{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Longest Substring of One Repeating Character"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #segment-tree #array #string #ordered-set"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #线段树 #数组 #字符串 #有序集合"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: longestRepeating"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #由单个字符重复的最长子字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong> 开始的字符串 <code>s</code> 。另给你一个下标从 <strong>0</strong> 开始、长度为 <code>k</code> 的字符串 <code>queryCharacters</code> ，一个下标从 <code>0</code> 开始、长度也是 <code>k</code> 的整数 <strong>下标</strong> 数组&nbsp;<code>queryIndices</code> ，这两个都用来描述 <code>k</code> 个查询。</p>\n",
    "\n",
    "<p>第 <code>i</code> 个查询会将 <code>s</code> 中位于下标 <code>queryIndices[i]</code> 的字符更新为 <code>queryCharacters[i]</code> 。</p>\n",
    "\n",
    "<p>返回一个长度为 <code>k</code> 的数组 <code>lengths</code> ，其中 <code>lengths[i]</code> 是在执行第 <code>i</code> 个查询 <strong>之后</strong> <code>s</code> 中仅由 <strong>单个字符重复</strong> 组成的 <strong>最长子字符串</strong> 的 <strong>长度</strong> <em>。</em></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"babacc\", queryCharacters = \"bcb\", queryIndices = [1,3,3]\n",
    "<strong>输出：</strong>[3,3,4]\n",
    "<strong>解释：</strong>\n",
    "- 第 1 次查询更新后 s = \"<em>b<strong>b</strong>b</em>acc\" 。由单个字符重复组成的最长子字符串是 \"bbb\" ，长度为 3 。\n",
    "- 第 2 次查询更新后 s = \"bbb<em><strong>c</strong>cc</em>\" 。由单个字符重复组成的最长子字符串是 \"bbb\" 或 \"ccc\"，长度为 3 。\n",
    "- 第 3 次查询更新后 s = \"<em>bbb<strong>b</strong></em>cc\" 。由单个字符重复组成的最长子字符串是 \"bbbb\" ，长度为 4 。\n",
    "因此，返回 [3,3,4] 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"abyzz\", queryCharacters = \"aa\", queryIndices = [2,1]\n",
    "<strong>输出：</strong>[2,3]\n",
    "<strong>解释：</strong>\n",
    "- 第 1 次查询更新后 s = \"ab<strong>a</strong><em>zz</em>\" 。由单个字符重复组成的最长子字符串是 \"zz\" ，长度为 2 。\n",
    "- 第 2 次查询更新后 s = \"<em>a<strong>a</strong>a</em>zz\" 。由单个字符重复组成的最长子字符串是 \"aaa\" ，长度为 3 。\n",
    "因此，返回 [2,3] 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>s</code> 由小写英文字母组成</li>\n",
    "\t<li><code>k == queryCharacters.length == queryIndices.length</code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>queryCharacters</code> 由小写英文字母组成</li>\n",
    "\t<li><code>0 &lt;= queryIndices[i] &lt; s.length</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [longest-substring-of-one-repeating-character](https://leetcode.cn/problems/longest-substring-of-one-repeating-character/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [longest-substring-of-one-repeating-character](https://leetcode.cn/problems/longest-substring-of-one-repeating-character/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"babacc\"\\n\"bcb\"\\n[1,3,3]', '\"abyzz\"\\n\"aa\"\\n[2,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        for i in range(1,len(s)):\n",
    "            if s[i-ans:i+1] in s[:i]:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        for i in range(1,len(s)):\n",
    "            if s[i-ans:i+1] in s[:i]:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        #Rabin-Karp harsh algorithm\n",
    "        def search(subString_length,letterNum,modulus,string_length, nums):\n",
    "            hash_enocode=0\n",
    "            for i in range(subString_length):\n",
    "                hash_enocode=(hash_enocode*letterNum+nums[i]) %modulus   \n",
    "            seen={hash_enocode}\n",
    "\n",
    "            aL= pow(letterNum,subString_length,modulus)\n",
    "            for start in range(1,string_length-subString_length+1):\n",
    "                hash_enocode=(hash_enocode*letterNum - nums[start-1]*aL+nums[start+subString_length-1])% modulus\n",
    "                if hash_enocode in seen:\n",
    "                    return start\n",
    "                seen.add(hash_enocode)\n",
    "            return -1\n",
    "\n",
    "        n=len(s)\n",
    "        nums=[ord(s[i])-ord('a') for i in range(n)]\n",
    "        a=26\n",
    "        modulus = 2**24\n",
    "\n",
    "        left, right=1,n\n",
    "        ans=0\n",
    "        while left<=right:\n",
    "            mid =left+(right-left)//2\n",
    "            if search(mid,a,modulus,n,nums)!=-1:\n",
    "                ans=mid\n",
    "                left=mid+1\n",
    "            else:\n",
    "                right=mid-1\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        def search(L):\n",
    "            seen = set()\n",
    "            h = 0\n",
    "            a = 26\n",
    "            al = pow(a, L, mod)\n",
    "\n",
    "            for i in range(L):\n",
    "                h = (h * a + ord(s[i])) % mod\n",
    "            \n",
    "            seen.add(h)\n",
    "\n",
    "            for i in range(1, len(s) - L + 1):\n",
    "                h = (h * a - ord(s[i - 1]) * al + ord(s[i + L - 1])) % mod\n",
    "\n",
    "                if h in seen:\n",
    "                    return i\n",
    "                seen.add(h)\n",
    "            \n",
    "            return -1\n",
    "        \n",
    "        left, right = 1, len(s)\n",
    "        mod = 10 ** 9 + 7\n",
    "        ans = 0\n",
    "\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "            pos = search(mid)\n",
    "\n",
    "            if pos != -1:\n",
    "                ans = mid\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        #Rabin-Karp harsh algorithm\n",
    "        def search(subString_length,letterNum,modulus,string_length, nums):\n",
    "            hash_enocode=0\n",
    "            for i in range(subString_length):\n",
    "                hash_enocode=(hash_enocode*letterNum+nums[i]) %modulus   \n",
    "            seen={hash_enocode}\n",
    "\n",
    "            aL= pow(letterNum,subString_length,modulus)\n",
    "            for start in range(1,string_length-subString_length+1):\n",
    "                hash_enocode=(hash_enocode*letterNum - nums[start-1]*aL+nums[start+subString_length-1])% modulus\n",
    "                if hash_enocode in seen:\n",
    "                    return start\n",
    "                seen.add(hash_enocode)\n",
    "            return -1\n",
    "\n",
    "        n=len(s)\n",
    "        nums=[ord(s[i])-ord('a') for i in range(n)]\n",
    "        a=26\n",
    "        modulus = 2**24\n",
    "\n",
    "        left, right=1,n\n",
    "        ans=0\n",
    "        while left+1<right:\n",
    "            mid =left+(right-left)//2\n",
    "            if search(mid,a,modulus,n,nums)!=-1:\n",
    "                ans=mid\n",
    "                left=mid\n",
    "            else:\n",
    "                right=mid\n",
    "        if search(right,a,modulus,n,nums)!=-1:\n",
    "            return right\n",
    "        if search(left,a,modulus,n,nums)!=-1:\n",
    "            return left\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "_MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        d = [ord(c) - ord(\"a\") for c in s]\n",
    "        def verify(l: int) -> bool:\n",
    "            if l == 0:\n",
    "                return True\n",
    "            h = 0\n",
    "            for i in range(l):\n",
    "                h = (h * 26 + d[i]) % _MOD\n",
    "            seen = {h}\n",
    "            p = pow(26, l, _MOD)\n",
    "            for i in range(n - l):\n",
    "                h = (h * 26 - d[i] * p + d[l + i] + _MOD) % _MOD\n",
    "                if h in seen:\n",
    "                    return True\n",
    "                seen.add(h)\n",
    "            return False\n",
    "        \n",
    "        l, r = 0, n\n",
    "        while l < r:\n",
    "            m = l + r + 1 >> 1\n",
    "            if verify(m):\n",
    "                l = m\n",
    "            else:\n",
    "                r = m - 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        def kmp(s):\n",
    "            j = 0\n",
    "            next = [0]*len(s)\n",
    "            for i in range(1,len(s)):\n",
    "                while j > 0 and s[i] != s[j]:\n",
    "                    j = next[j-1]\n",
    "                if s[i] == s[j]:\n",
    "                    j += 1\n",
    "                next[i] = j\n",
    "            return next\n",
    "        m = 0\n",
    "        for i in range(len(s)):\n",
    "            now = max(kmp(s[i:]))\n",
    "            if now > m:\n",
    "                m = now\n",
    "        return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        def kmp(s):\n",
    "            j = 0\n",
    "            next = [0]*len(s)\n",
    "            for i in range(1,len(s)):\n",
    "                while j > 0 and s[i] != s[j]:\n",
    "                    j = next[j-1]\n",
    "                if s[i] == s[j]:\n",
    "                    j += 1\n",
    "                next[i] = j\n",
    "            return next\n",
    "        m = 0\n",
    "        for i in range(len(s)):\n",
    "            now = max(kmp(s[i:]))\n",
    "            if now > m:\n",
    "                m = now\n",
    "        return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def search(self, L: int, n: int, S: str) -> str:\n",
    "        \"\"\"\n",
    "        Search a substring of given length\n",
    "        that occurs at least 2 times.\n",
    "        @return start position if the substring exits and -1 otherwise.\n",
    "        \"\"\"\n",
    "        # seen = set()\n",
    "        # for start in range(0, n - L + 1):\n",
    "        #     tmp = S[start:start + L]\n",
    "        #     if tmp in seen:\n",
    "        #         return start\n",
    "        #     seen.add(tmp)\n",
    "        # return -1\n",
    "        seen = set()\n",
    "        for start in range(0, n - L + 1):\n",
    "            tmp = S[start : start + L]\n",
    "            h = hash(tmp)\n",
    "            if h in seen:\n",
    "                return start\n",
    "            seen.add(h)\n",
    "        return -1\n",
    "\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "\n",
    "        l, r = 1, n\n",
    "        while l < r:\n",
    "            L = l + (r - l) // 2\n",
    "            if self.search(L, n, s) != -1:\n",
    "                l = L + 1\n",
    "            else:\n",
    "                r = L\n",
    "        return l - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        def ok(t):\n",
    "            mp = {}\n",
    "            for i in range(0, n-t+1):\n",
    "                if s[i:i+t][::] in mp:\n",
    "                    return False\n",
    "                mp[s[i:i+t][::]] = True\n",
    "            return True\n",
    "        return bisect_left(range(1, n + 1), True, key=ok)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        def ok(t):\n",
    "            mp = {}\n",
    "            for i in range(0, n-t+1):\n",
    "                if s[i:i+t] in mp:\n",
    "                    return False\n",
    "                mp[s[i:i+t]] = True\n",
    "            return True\n",
    "        return bisect_left(range(1, n), True, key=ok)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        l,r=0,n-1\n",
    "        def check(mid):\n",
    "            if mid==0:return True\n",
    "            c=set()\n",
    "            for j in range(mid,n+1):\n",
    "                if s[j-mid:j]in c:return True\n",
    "                c.add(s[j-mid:j])\n",
    "            return False\n",
    "        res=0\n",
    "        while l<=r:\n",
    "            mid=(l+r)>>1\n",
    "            if check(mid):\n",
    "                res=mid\n",
    "                l=mid+1\n",
    "            else:\n",
    "                r=mid-1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        def ok(t):\n",
    "            mp = {}\n",
    "            for i in range(0, n-t+1):\n",
    "                if s[i:i+t] in mp:\n",
    "                    return False\n",
    "                mp[s[i:i+t]] = True\n",
    "            return True\n",
    "        return bisect_left(range(1, n), True, key=ok)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def search(self, L: int, n: int, S: str) -> str:\n",
    "        \"\"\"\n",
    "        Search a substring of given length\n",
    "        that occurs at least 2 times.\n",
    "        @return start position if the substring exits and -1 otherwise.\n",
    "        \"\"\"\n",
    "        seen = set()\n",
    "        for start in range(0, n - L + 1):\n",
    "            tmp = S[start:start + L]\n",
    "            if tmp in seen:\n",
    "                return start\n",
    "            seen.add(tmp)\n",
    "        return -1\n",
    "        \n",
    "    def longestRepeatingSubstring(self, S: str) -> str:\n",
    "        n = len(S)\n",
    "        \n",
    "        # binary search, L = repeating string length\n",
    "        left, right = 1, n\n",
    "        while left <= right:\n",
    "            L = left + (right - left) // 2\n",
    "            if self.search(L, n, S) != -1:\n",
    "                left = L + 1\n",
    "            else:\n",
    "                right = L - 1\n",
    "               \n",
    "        return left - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        def check(size) -> bool:\n",
    "            seen = set()\n",
    "            for l in range(len(s) - size + 1):\n",
    "                if s[l:l + size] in seen:\n",
    "                    return True\n",
    "                seen.add(s[l:l + size])\n",
    "            return False\n",
    "\n",
    "        l, r = 0, len(s)\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            if check(mid):\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def search(self, L: int, n: int, S: str) -> str:\n",
    "        \"\"\"\n",
    "        Search a substring of given length\n",
    "        that occurs at least 2 times.\n",
    "        @return start position if the substring exits and -1 otherwise.\n",
    "        \"\"\"\n",
    "        seen = set()\n",
    "        for start in range(0, n - L + 1):\n",
    "            tmp = S[start:start + L]\n",
    "            if tmp in seen:\n",
    "                return start\n",
    "            seen.add(tmp)\n",
    "        return -1\n",
    "        \n",
    "    def longestRepeatingSubstring(self, S: str) -> str:\n",
    "        n = len(S)\n",
    "        \n",
    "        # binary search, L = repeating string length\n",
    "        left, right = 1, n\n",
    "        while left <= right:\n",
    "            L = left + (right - left) // 2\n",
    "            if self.search(L, n, S) != -1:\n",
    "                left = L + 1\n",
    "            else:\n",
    "                right = L - 1\n",
    "               \n",
    "        return left - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        l, r = -1, n + 1\n",
    "\n",
    "        def find(l):\n",
    "            st = set()\n",
    "            for i in range(n - l + 1):\n",
    "                sub = s[i: i + l]\n",
    "                if sub in st:\n",
    "                    return True\n",
    "                st.add(sub)\n",
    "            return False\n",
    "\n",
    "        while l + 1 < r:\n",
    "            m = (l + r) // 2\n",
    "            if find(m):\n",
    "                l = m\n",
    "            else:\n",
    "                r = m\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def search(self, L: int, n: int, S: str) -> str:\n",
    "        \"\"\"\n",
    "        Search a substring of given length\n",
    "        that occurs at least 2 times.\n",
    "        @return start position if the substring exits and -1 otherwise.\n",
    "        \"\"\"\n",
    "        seen = set()\n",
    "        for start in range(0, n - L + 1):\n",
    "            tmp = S[start:start + L]\n",
    "            if tmp in seen:\n",
    "                return start\n",
    "            seen.add(tmp)\n",
    "        return -1\n",
    "        \n",
    "    def longestRepeatingSubstring(self, S: str) -> str:\n",
    "        n = len(S)\n",
    "        \n",
    "        # binary search, L = repeating string length\n",
    "        left, right = 1, n\n",
    "        while left <= right:\n",
    "            L = left + (right - left) // 2\n",
    "            if self.search(L, n, S) != -1:\n",
    "                left = L + 1\n",
    "            else:\n",
    "                right = L - 1\n",
    "               \n",
    "        return left - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        def check(t):\n",
    "            mp = {}\n",
    "            for i in range(0, n-t+1):\n",
    "                if s[i:i+t][::] in mp:\n",
    "                    return True\n",
    "                mp[s[i:i+t][::]] = True\n",
    "            return False\n",
    "        lo, hi = 1, n\n",
    "        while lo < hi:\n",
    "            mid = (lo + hi) >> 1\n",
    "            if not check(mid):\n",
    "                hi = mid\n",
    "            else:\n",
    "                lo = mid + 1\n",
    "        return lo - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        def search(k):\n",
    "            # print(f\"call({k})\")\n",
    "            visited = set()\n",
    "            for i in range(len(s)-k+1):\n",
    "                if s[i:i+k] in visited:\n",
    "                    return True\n",
    "                else:\n",
    "                    visited.add(s[i:i+k])\n",
    "            return False\n",
    "\n",
    "        low = 1\n",
    "        high = len(s)-1\n",
    "        ans = 0\n",
    "        while low <= high:\n",
    "            mid = (low+high)//2\n",
    "            if search(mid):\n",
    "                ans = mid\n",
    "                low = mid + 1\n",
    "            else:\n",
    "                high = mid - 1\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        \n",
    "        def check(S,res):\n",
    "            record = set([S[i:i+res] for i in range(len(S)-res+1)])\n",
    "            print((len(record) != len(S)-res+1))\n",
    "            return (len(record) != len(S)-res+1)\n",
    "        S = s\n",
    "        left = 1\n",
    "        right = len(S)-1\n",
    "        while left <= right:\n",
    "            #print(left,right)\n",
    "            mid = (left+right+1)//2\n",
    "            if check(S,right):\n",
    "                return right\n",
    "            else:\n",
    "                if check(S,mid):\n",
    "                    left = mid\n",
    "                else:\n",
    "                    right = mid-1\n",
    "        return 0         \n",
    "\n",
    "\n",
    "        n = len(s)\n",
    "        for k in range(n - 1, 0, -1):\n",
    "            pre = set()\n",
    "            for i in range(n - k + 1):\n",
    "                if s[i: i + k] in pre:\n",
    "                    return k\n",
    "                pre.add(s[i: i + k])\n",
    "        return 0\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        ln = 0\n",
    "        low, high = ln, n - 1\n",
    "\n",
    "        def f(x):\n",
    "            seen = set()\n",
    "            for i in range(n - x + 1):\n",
    "                tmp = s[i: i + x]\n",
    "                if tmp in seen:\n",
    "                    return True \n",
    "                seen.add(tmp)\n",
    "            return False \n",
    "        \n",
    "        while low <= high:\n",
    "            mid = (low + high) // 2\n",
    "            if f(mid):\n",
    "                low = mid + 1\n",
    "                ln = mid \n",
    "            else:\n",
    "                high = mid - 1\n",
    "        return ln \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        l, r = 0, n - 1\n",
    "        while l <= r and r > 0:\n",
    "            mid = l + (r - l) // 2\n",
    "            if self.check(mid, s, n) == -1:\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return r\n",
    "\n",
    "    def check(self, L, s, n):\n",
    "        hashSet = set()\n",
    "        for i in range(n - L + 1):\n",
    "            if s[i:i + L] in hashSet:\n",
    "                return i\n",
    "            else:\n",
    "                hashSet.add(s[i:i + L])\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "a b c a b c\n",
    "1 2 3 4 5 6\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        left, right = 1, len(s)\n",
    "\n",
    "        def search(mid):\n",
    "            visited = set()\n",
    "\n",
    "            for i in range(len(s) - mid + 1):\n",
    "                temp = s[i :mid + i]\n",
    "                if temp in visited:\n",
    "                    return i\n",
    "                visited.add(temp)\n",
    "\n",
    "            return -1\n",
    "\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            # 找到一个repeating substring, 就往后面找看看有没有更长的substring\n",
    "            if search(mid) != -1:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        \n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        def check(n):\n",
    "            D = set()\n",
    "            for i in range(len(s)-n+1):\n",
    "                if s[i:i+n] in D:\n",
    "                    return True\n",
    "                D.add(s[i:i+n])\n",
    "            return False\n",
    "        N = len(s)\n",
    "        start, end = 1, N\n",
    "        ans = 0\n",
    "        while start < end:\n",
    "            mid = start + (end - start) // 2\n",
    "            if check(mid):\n",
    "                ans = mid\n",
    "                start = mid + 1\n",
    "            else:\n",
    "                end = mid - 1\n",
    "        if check(start):\n",
    "            ans = start\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        @lru_cache(None)\n",
    "        def check(k):\n",
    "            pre = set()\n",
    "            for i in range(n - k + 1):\n",
    "                cur = s[i: i + k]\n",
    "                if cur in pre:\n",
    "                    return True\n",
    "                pre.add(cur)\n",
    "            return False\n",
    "\n",
    "        n = len(s)\n",
    "        low = 1\n",
    "        high = n - 1\n",
    "        while low < high - 1:\n",
    "            mid = low + (high - low) // 2\n",
    "            if check(mid):\n",
    "                low = mid\n",
    "            else:\n",
    "                high = mid\n",
    "        if check(high):\n",
    "            return high\n",
    "        if check(low):\n",
    "            return low\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        for ln in range(n - 1, 1, -1):\n",
    "            cnt = Counter()\n",
    "            for i in range(n - ln + 1):\n",
    "                cnt[s[i: i + ln]] += 1\n",
    "            mx = max(cnt.values())\n",
    "            if mx > 1:\n",
    "                return ln \n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        for k in range(n - 1, 0, -1):\n",
    "            pre = set()\n",
    "            for i in range(n - k + 1):\n",
    "                if s[i: i + k] in pre:\n",
    "                    return k\n",
    "                pre.add(s[i: i + k])\n",
    "        return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        def search(k):\n",
    "            # print(f\"call({k})\")\n",
    "            visited = set()\n",
    "            for i in range(len(s)-k+1):\n",
    "                if s[i:i+k] in visited:\n",
    "                    return True\n",
    "                else:\n",
    "                    visited.add(s[i:i+k])\n",
    "            return False\n",
    "\n",
    "        \n",
    "        for k in range(len(s)-1, -1, -1):\n",
    "            if search(k):\n",
    "                return k\n",
    "\n",
    "        return 0\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class suffix_array:\n",
    "    def __init__(self, n: int, m: int, s):\n",
    "        self.N = 10 ** 5 + 10\n",
    "        self.n = n\n",
    "        self.m = m                                  #最大的字母，ascii码\n",
    "        self.s = s\n",
    "        self.sa = [0 for _ in range(self.N)]         #排名为i的后缀，开头的index（从1开始计）\n",
    "        self.rk = [0 for _ in range(self.N)]         #当前长度下，i开始的后缀的，排名\n",
    "        self.height = [0 for _ in range(self.N)]     #rk是i-1 和 i 的lcp\n",
    "        self.x = [0 for _ in range(self.N)]\n",
    "        self.y = [0 for _ in range(self.N)]\n",
    "        self.c = [0 for _ in range(self.N)]\n",
    "    \n",
    "    def get_sa(self) -> None:\n",
    "        for i in range(1, self.n + 1):\n",
    "            self.x[i] = ord(self.s[i])\n",
    "            self.c[self.x[i]] += 1\n",
    "        for i in range(2, self.m + 1):  self.c[i] += self.c[i - 1]\n",
    "        for i in range(self.n, 0, -1):\n",
    "            self.sa[self.c[self.x[i]]] = i\n",
    "            self.c[self.x[i]] -= 1\n",
    "        \n",
    "        k = 1\n",
    "        while k <= self.n: \n",
    "            num = 0\n",
    "            for i in range(self.n - k + 1, self.n + 1, 1):\n",
    "                num += 1\n",
    "                self.y[num] = i\n",
    "            for i in range(1, self.n + 1):\n",
    "                if self.sa[i] > k:\n",
    "                    num += 1\n",
    "                    self.y[num] = self.sa[i] - k\n",
    "            \n",
    "            for i in range(1, self.m + 1):  self.c[i] = 0\n",
    "            for i in range(1, self.n + 1):  self.c[self.x[i]] += 1\n",
    "            for i in range(2, self.m + 1):  self.c[i] += self.c[i - 1]\n",
    "            \n",
    "            for i in range(self.n, 0, -1):\n",
    "                self.sa[self.c[self.x[self.y[i]]]] = self.y[i]\n",
    "                self.c[self.x[self.y[i]]] -= 1\n",
    "                self.y[i] = 0\n",
    "            \n",
    "            self.x, self.y = self.y, self.x\n",
    "            self.x[self.sa[1]] = 1\n",
    "            num = 1\n",
    "\n",
    "            for i in range(2, self.n + 1):\n",
    "                if (self.y[self.sa[i]] == self.y[self.sa[i - 1]]) and (self.y[self.sa[i] + k] == self.y[self.sa[i - 1] + k]):\n",
    "                    self.x[self.sa[i]] = num\n",
    "                else:\n",
    "                    num += 1\n",
    "                    self.x[self.sa[i]] = num\n",
    "\n",
    "            if num == self.n:\n",
    "                break\n",
    "            self.m = num\n",
    "\n",
    "            k *= 2\n",
    "\n",
    "    def get_height(self) -> None:\n",
    "        for i in range(1, self.n + 1):\n",
    "            self.rk[self.sa[i]] = i\n",
    "        k = 0\n",
    "        for i in range(1, self.n + 1):\n",
    "            if self.rk[i] == 1:\n",
    "                continue\n",
    "            if k > 0:\n",
    "                k -= 1\n",
    "            j = self.sa[self.rk[i] - 1]\n",
    "            while (i + k <= self.n) and (j + k <= self.n) and (self.s[i + k] == self.s[j + k]):\n",
    "                k += 1\n",
    "            self.height[self.rk[i]] = k\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        n = len(s)\n",
    " \n",
    "        SA = suffix_array(n, ord('z'), \" \" + s)     \n",
    "        SA.get_sa()\n",
    "        SA.get_height()\n",
    "\n",
    "        res = 0\n",
    "        for i in range(2, n + 1):\n",
    "            if SA.height[i] > res:\n",
    "                res = SA.height[i]\n",
    "  \n",
    "        return res\n",
    "\n",
    "# 作者：HanXin\n",
    "# 链接：https://leetcode.cn/problems/longest-repeating-substring/solutions/635439/c-python-3-quan-shi-tao-lu-biao-zhun-er-vbgss/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        f = [[0]*n for _ in range(n)]\n",
    "        res = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                if s[i]==s[j]:\n",
    "                    f[i][j] = f[i-1][j-1]+1\n",
    "                    res = max(res, f[i][j])\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[None] * n for _ in range(n)]\n",
    "        res = 0\n",
    "        for i in range(n - 1):\n",
    "            for j in range(i + 1, n):\n",
    "                if s[i] == s[j]:\n",
    "                    if i == 0:\n",
    "                        dp[i][j] = 1\n",
    "                    else:\n",
    "                        #print(i, j, dp[i][j], dp[i - 1][j - 1])\n",
    "                        dp[i][j] = dp[i - 1][j - 1] + 1\n",
    "                else:\n",
    "                        dp[i][j] = 0\n",
    "\n",
    "                res = max(res, dp[i][j])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        res = 0\n",
    "        for i in range(n - 1):\n",
    "            for j in range(i + 1, n):\n",
    "                if s[i] == s[j]:\n",
    "                    if i == 0:\n",
    "                        dp[i][j] = 1\n",
    "                    else:\n",
    "                        dp[i][j] = dp[i - 1][j - 1] + 1\n",
    "                res = max(res, dp[i][j])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        dp=[[0 for j in range(n)] for i in range(n)]\n",
    "        ans=0\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                if s[i]==s[j]:\n",
    "                    if i==0:dp[i][j]=1\n",
    "                    else:dp[i][j]=dp[i-1][j-1]+1\n",
    "                ans=max(ans,dp[i][j])\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "\n",
    "        dp = [[0 for j in range(len(s))] for i in range(len(s))]\n",
    "        ans = 0\n",
    "        for i in range(len(s)):\n",
    "            for j in range(i+1,len(s)): # j至少等于i+1，这样两个子串必定是不完全重叠的\n",
    "                if s[i]==s[j]:\n",
    "                    dp[i][j]=dp[i-1][j-1]+1 if i else 1\n",
    "                    ans = max(ans,dp[i][j]) # 最终答案可能落在任意位置，因此实时更新\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        dp=[[0 for j in range(n)] for i in range(n)]\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                if s[i]==s[j]:\n",
    "                    if i==0:dp[i][j]=1\n",
    "                    else:dp[i][j]=dp[i-1][j-1]+1\n",
    "                ans=max(ans,dp[i][j])\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "\n",
    "        dp = [[0 for j in range(len(s))] for i in range(len(s))]\n",
    "        ans = 0\n",
    "\n",
    "        for i in range(len(s)):\n",
    "            for j in range(i+1, len(s)):\n",
    "                if s[i] == s[j]:\n",
    "                    dp[i][j] = dp[i-1][j-1]+1 if i else 1\n",
    "                    ans = max(ans, dp[i][j])\n",
    "        \n",
    "        \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        dp = [[0 for j in range(len(s))] for _ in range(len(s))]\n",
    "        ans = 0 \n",
    "        for i in range(len(s)):\n",
    "            for j in range(i + 1, len(s)):\n",
    "                if s[i] == s[j]:\n",
    "                    dp[i][j] = dp[i-1][j-1] + 1 if i else 1\n",
    "                    ans = max(ans, dp[i][j])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        dp = [[0 for j in range(len(s))] for i in range(len(s))]\n",
    "        ans = 0\n",
    "        for i in range(len(s)):\n",
    "            for j in range(i+1, len(s)):\n",
    "                if s[i] == s[j]:\n",
    "                    dp[i][j] = dp[i-1][j-1] + 1 if i else 1\n",
    "                    ans = max(ans, dp[i][j])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        dp = [[0 for i in range(len(s))] for j in range(len(s))]\n",
    "        ans = 0\n",
    "        for i in range(len(s)):\n",
    "            for j in range(i+1, len(s)):\n",
    "                if s[i] == s[j]:\n",
    "                    dp[i][j] = dp[i-1][j-1] + 1 if i else 1\n",
    "                ans = max(ans, dp[i][j])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        s1,s2 = copy.deepcopy(s),copy.deepcopy(s)\n",
    "        n,m = len(s1),len(s2)\n",
    "        dp = [[0]*(m+1) for i in range(n+1)]\n",
    "\n",
    "        mmax = 0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if s1[i]==s2[j] and i!=j:\n",
    "                    dp[i+1][j+1] = dp[i][j]+1\n",
    "                    if dp[i+1][j+1]>mmax:\n",
    "                        mmax = dp[i+1][j+1]\n",
    "        \n",
    "        return mmax\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, S: str) -> int:\n",
    "        from collections import defaultdict\n",
    "        mem = defaultdict(lambda: 0, {})\n",
    "        length = len(S)\n",
    "        for i in range(1, length + 1):\n",
    "            for j in range(i+1, length + 1):\n",
    "                if S[i-1] == S[j-1]:\n",
    "                    mem[i, j] = mem[i -1, j-1] + 1\n",
    "        values = [0] + list(mem.values())\n",
    "        return max(values)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        tree = {}\n",
    "        ans = 0\n",
    "\n",
    "        for i in range(len(s)):\n",
    "            cur = tree\n",
    "            cnt = 0\n",
    "            for c in s[i:]:\n",
    "                if c in cur:\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    cur[c] = {}\n",
    "                cur = cur[c]\n",
    "            ans = max(ans, cnt)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        tree = {}\n",
    "        ans = 0\n",
    "        n = len(s)\n",
    "\n",
    "        for i in range(n):\n",
    "            if n-i <= ans:\n",
    "                break\n",
    "\n",
    "            cur = tree\n",
    "            cnt = 0\n",
    "            for c in s[i:]:\n",
    "                if c in cur:\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    cur[c] = {}\n",
    "                cur = cur[c]\n",
    "            if cnt > ans:\n",
    "                ans = cnt\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeatingSubstring(self, s: str) -> int:\n",
    "        tree = {}\n",
    "        ans = 0\n",
    "        n = len(s)\n",
    "\n",
    "        for i in range(n):\n",
    "            if n-i <= ans:\n",
    "                break\n",
    "\n",
    "            cur = tree\n",
    "            cnt = 0\n",
    "            for c in s[i:]:\n",
    "                if c in cur:\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    cur[c] = {}\n",
    "                cur = cur[c]\n",
    "            ans = max(ans, cnt)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeating(self, s: str, queryCharacters: str, queryIndices: List[int]) -> List[int]:\n",
    "        from sortedcontainers import SortedList\n",
    "        L = len(s)\n",
    "        s = list(s)\n",
    "        lens = SortedList()\n",
    "        starts = SortedList()\n",
    "        off = 0\n",
    "        for c, grp in groupby(s):\n",
    "            _len = sum(1 for _ in grp)\n",
    "            starts.add(off)\n",
    "            lens.add(_len)\n",
    "            off += _len\n",
    "        starts.add(off)\n",
    "        res = [0]*len(queryCharacters)\n",
    "        for resOff, (i, c) in enumerate(zip(queryIndices, queryCharacters)):\n",
    "            if c != s[i]:\n",
    "                s[i] = c\n",
    "                off = starts.bisect_right(i) - 1\n",
    "                left = starts[off]\n",
    "                right = starts[off+1] - 1\n",
    "                nextRight = starts[off+2] - 1 if right + 1 < L else 0\n",
    "                lens.remove(right - left + 1) # -1\n",
    "                if left < i < right: # +2, +3\n",
    "                    starts.add(i)\n",
    "                    starts.add(i+1)\n",
    "                    lens.add(i-left)\n",
    "                    lens.add(right - i)\n",
    "                    lens.add(1)\n",
    "                elif left == i == right:\n",
    "                    prevLen = nextLen = 0\n",
    "                    if left and s[left-1] == c:\n",
    "                        prevLen = left - starts[off-1] + 1\n",
    "                        lens.remove(prevLen - 1)\n",
    "                        starts.remove(left)\n",
    "                    if right + 1 < L and s[right+1] == c:\n",
    "                        # print(nextRight, right, starts[off+2])\n",
    "                        nextLen = nextRight - right + 1\n",
    "                        lens.remove(nextLen-1) \n",
    "                        starts.remove(right+1)\n",
    "                    if prevLen and nextLen:\n",
    "                        lens.add(prevLen + nextLen - 1)\n",
    "                    else:\n",
    "                        lens.add(prevLen or nextLen or 1)\n",
    "                elif left == i: # i < right\n",
    "                    starts.add(left + 1)\n",
    "                    lens.add(right - left)\n",
    "                    if left and s[left-1] == c:\n",
    "                        prevLen = left - starts[off-1] + 1\n",
    "                        lens.remove(prevLen - 1)\n",
    "                        lens.add(prevLen)\n",
    "                        starts.remove(left)\n",
    "                    else:\n",
    "                        lens.add(1)\n",
    "                else: # left < i == right:\n",
    "                    lens.add(right - left)\n",
    "                    starts.add(right)\n",
    "                    if right + 1 < L and s[right+1] == c:\n",
    "                        nextLen = nextRight - right + 1\n",
    "                        lens.remove(nextLen-1) \n",
    "                        lens.add(nextLen)\n",
    "                        starts.remove(right+1)\n",
    "                    else:\n",
    "                        lens.add(1)\n",
    "            res[resOff] = lens[-1]\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SegmentTreeLongestSubSame:\n",
    "    # 模板：单点字母更新，最长具有相同字母的连续子数组查询\n",
    "    def __init__(self, n, lst):\n",
    "        self.n = n\n",
    "        self.lst = lst\n",
    "        # 注意深浅拷贝的问题\n",
    "        self.pref = [0] * 4 * n\n",
    "        self.suf = [0] * 4 * n\n",
    "        self.ma = [0] * 4 * n\n",
    "        self.build()\n",
    "        return\n",
    "\n",
    "    def build(self):\n",
    "        # 使用数组初始化线段树\n",
    "        stack = [[0, self.n - 1, 1]]\n",
    "        while stack:\n",
    "            s, t, ind = stack.pop()\n",
    "            if ind >= 0:\n",
    "                if s == t:\n",
    "                    self.make_tag(ind)\n",
    "                else:\n",
    "                    stack.append([s, t, ~ind])\n",
    "                    m = s + (t - s) // 2\n",
    "                    stack.append([s, m, 2 * ind])\n",
    "                    stack.append([m + 1, t, 2 * ind + 1])\n",
    "            else:\n",
    "                ind = ~ind\n",
    "                self.push_up(ind, s, t)\n",
    "        return\n",
    "\n",
    "    def make_tag(self, i):\n",
    "        self.pref[i] = 1\n",
    "        self.suf[i] = 1\n",
    "        self.ma[i] = 1\n",
    "        return\n",
    "\n",
    "    def push_up(self, i, s, t):\n",
    "        m = s + (t - s) // 2\n",
    "        # [s, m] 与 [m+1, t]\n",
    "        self.pref[i] = self.pref[2 * i]\n",
    "        if self.pref[2 * i] == m - s + 1 and self.lst[m] == self.lst[m + 1]:\n",
    "            self.pref[i] += self.pref[2 * i + 1]\n",
    "\n",
    "        self.suf[i] = self.suf[2 * i + 1]\n",
    "        if self.suf[2 * i + 1] == t - m and self.lst[m] == self.lst[m + 1]:\n",
    "            self.suf[i] += self.suf[2 * i]\n",
    "\n",
    "        a, b = self.pref[i], self.suf[i]\n",
    "        a = a if a > b else b\n",
    "        if self.lst[m] == self.lst[m + 1]:\n",
    "            b = self.suf[2 * i] + self.pref[2 * i + 1]\n",
    "            a = a if a > b else b\n",
    "\n",
    "        b = self.ma[2 * i]\n",
    "        a = a if a > b else b\n",
    "        b = self.ma[2 * i + 1]\n",
    "        a = a if a > b else b\n",
    "        self.ma[i] = a\n",
    "        return\n",
    "\n",
    "    def update_point(self, left, right, s, t, val, i):\n",
    "        # 更新单点最小值\n",
    "        self.lst[left] = val\n",
    "        stack = []\n",
    "        while True:\n",
    "            stack.append([s, t, i])\n",
    "            if s == t:\n",
    "                self.make_tag(i)\n",
    "                break\n",
    "            m = s + (t - s) // 2\n",
    "            if left <= m:  # 注意左右子树的边界与范围\n",
    "                s, t, i = s, m, 2 * i\n",
    "            if right > m:\n",
    "                s, t, i = m + 1, t, 2 * i + 1\n",
    "        stack.pop()\n",
    "        while stack:\n",
    "            s, t, i = stack.pop()\n",
    "            self.push_up(i, s, t)\n",
    "        assert i == 1\n",
    "        return self.ma[i]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeating(self, s: str, queryCharacters: str, queryIndices: List[int]) -> List[int]:\n",
    "        n = len(s)\n",
    "        tree = SegmentTreeLongestSubSame(n, [ord(w) - ord(\"a\") for w in s])\n",
    "        ans = []\n",
    "        for i, w in zip(queryIndices, queryCharacters):\n",
    "            if tree.lst[i] == w:\n",
    "                ans.append(tree.ma[1])\n",
    "                continue\n",
    "            ans.append(tree.update_point(i, i, 0, n - 1, ord(w) - ord(\"a\"), 1))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SegmentTreeLongestSubSame:\n",
    "    # 模板：单点字母更新，最长具有相同字母的连续子数组查询\n",
    "    def __init__(self, n, lst):\n",
    "        self.n = n\n",
    "        self.lst = lst\n",
    "        # 注意深浅拷贝的问题\n",
    "        self.pref = [0]*4*n\n",
    "        self.suf = [0]*4*n\n",
    "        self.ma = [0]*4*n\n",
    "        self.build()\n",
    "        return\n",
    "\n",
    "    def build(self):\n",
    "        # 使用数组初始化线段树\n",
    "        stack = [[0, self.n - 1, 1]]\n",
    "        while stack:\n",
    "            s, t, ind = stack.pop()\n",
    "            if ind >= 0:\n",
    "                if s == t:\n",
    "                    self.make_tag(ind)\n",
    "                else:\n",
    "                    stack.append([s, t, ~ind])\n",
    "                    m = s + (t - s) // 2\n",
    "                    stack.append([s, m, 2 * ind])\n",
    "                    stack.append([m + 1, t, 2 * ind + 1])\n",
    "            else:\n",
    "                ind = ~ind\n",
    "                self.push_up(ind, s, t)\n",
    "        return\n",
    "\n",
    "    def make_tag(self, i):\n",
    "        self.pref[i] = 1\n",
    "        self.suf[i] = 1\n",
    "        self.ma[i] = 1\n",
    "        return\n",
    "\n",
    "    def push_up(self, i, s, t):\n",
    "        m = s + (t - s) // 2\n",
    "        # [s, m] 与 [m+1, t]\n",
    "        self.pref[i] = self.pref[2*i]\n",
    "        if self.pref[2*i] == m - s + 1 and self.lst[m] == self.lst[m+1]:\n",
    "            self.pref[i] += self.pref[2*i+1]\n",
    "\n",
    "        self.suf[i] = self.suf[2 * i + 1]\n",
    "        if self.suf[2 * i + 1] == t - m and self.lst[m] == self.lst[m + 1]:\n",
    "            self.suf[i] += self.suf[2 * i]\n",
    "        \n",
    "        a, b = self.pref[i], self.suf[i]\n",
    "        a = a if a > b else b\n",
    "        if self.lst[m] == self.lst[m+1]:\n",
    "            b = self.suf[2*i] + self.pref[2*i+1]\n",
    "            a = a if a > b else b\n",
    "\n",
    "        b = self.ma[2*i]\n",
    "        a = a if a > b else b\n",
    "        b = self.ma[2*i+1]\n",
    "        a = a if a > b else b\n",
    "        self.ma[i] = a\n",
    "        return\n",
    "\n",
    "    def update_point(self, left, right, s, t, val, i):\n",
    "        # 更新单点最小值\n",
    "        self.lst[left] = val\n",
    "        stack = []\n",
    "        while True:\n",
    "            stack.append([s, t, i])\n",
    "            if s == t:\n",
    "                self.make_tag(i)\n",
    "                break\n",
    "            m = s + (t - s) // 2\n",
    "            if left <= m:  # 注意左右子树的边界与范围\n",
    "                s, t, i = s, m, 2 * i\n",
    "            if right > m:\n",
    "                s, t, i = m + 1, t, 2 * i + 1\n",
    "        stack.pop()\n",
    "        while stack:\n",
    "            s, t, i = stack.pop()\n",
    "            self.push_up(i, s, t)\n",
    "        assert i == 1\n",
    "        return self.ma[i]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeating(self, s: str, queryCharacters: str, queryIndices: List[int]) -> List[int]:\n",
    "        n = len(s)\n",
    "        tree = SegmentTreeLongestSubSame(n, [ord(w) - ord(\"a\") for w in s])\n",
    "        ans = []\n",
    "        for i, w in zip(queryIndices, queryCharacters):\n",
    "            ans.append(tree.update_point(i, i, 0, n - 1, ord(w) - ord(\"a\"), 1))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SegmentTreeLongestSubSame:\n",
    "    # 模板：单点字母更新，最长具有相同字母的连续子数组查询\n",
    "    def __init__(self, n, lst):\n",
    "        self.n = n\n",
    "        self.lst = lst\n",
    "        # 注意深浅拷贝的问题\n",
    "        self.pref = [0]*4*n\n",
    "        self.suf = [0]*4*n\n",
    "        self.ma = [0]*4*n\n",
    "        self.build()\n",
    "        return\n",
    "\n",
    "    def build(self):\n",
    "        # 使用数组初始化线段树\n",
    "        stack = [[0, self.n - 1, 1]]\n",
    "        while stack:\n",
    "            s, t, ind = stack.pop()\n",
    "            if ind >= 0:\n",
    "                if s == t:\n",
    "                    self.make_tag(ind)\n",
    "                else:\n",
    "                    stack.append([s, t, ~ind])\n",
    "                    m = s + (t - s) // 2\n",
    "                    stack.append([s, m, 2 * ind])\n",
    "                    stack.append([m + 1, t, 2 * ind + 1])\n",
    "            else:\n",
    "                ind = ~ind\n",
    "                self.push_up(ind, s, t)\n",
    "        return\n",
    "\n",
    "    @staticmethod\n",
    "    def min(a, b):\n",
    "        return a if a < b else b\n",
    "\n",
    "    @staticmethod\n",
    "    def max(a, b):\n",
    "        return a if a > b else b\n",
    "\n",
    "    def make_tag(self, i):\n",
    "        self.pref[i] = 1\n",
    "        self.suf[i] = 1\n",
    "        self.ma[i] = 1\n",
    "        return\n",
    "\n",
    "    def push_up(self, i, s, t):\n",
    "        m = s + (t - s) // 2\n",
    "        # [s, m] 与 [m+1, t]\n",
    "        self.pref[i] = self.pref[2*i]\n",
    "        if self.pref[2*i] == m - s + 1 and self.lst[m] == self.lst[m+1]:\n",
    "            self.pref[i] += self.pref[2*i+1]\n",
    "\n",
    "        self.suf[i] = self.suf[2 * i + 1]\n",
    "        if self.suf[2 * i + 1] == t - m and self.lst[m] == self.lst[m + 1]:\n",
    "            self.suf[i] += self.suf[2 * i]\n",
    "\n",
    "        ma1 = self.max(self.pref[i], self.suf[i])\n",
    "        if self.lst[m] == self.lst[m+1]:\n",
    "            ma1 = self.max(ma1, self.suf[2*i]+self.pref[2*i+1])\n",
    "        ma2 = self.max(self.ma[2*i], self.ma[2*i+1])\n",
    "        self.ma[i] = self.max(ma1, ma2)\n",
    "        return\n",
    "\n",
    "    def update_point(self, left, right, s, t, val, i):\n",
    "        # 更新单点最小值\n",
    "        self.lst[left] = val\n",
    "        stack = []\n",
    "        while True:\n",
    "            stack.append([s, t, i])\n",
    "            if s == t:\n",
    "                self.make_tag(i)\n",
    "                break\n",
    "            m = s + (t - s) // 2\n",
    "            if left <= m:  # 注意左右子树的边界与范围\n",
    "                s, t, i = s, m, 2 * i\n",
    "            if right > m:\n",
    "                s, t, i = m + 1, t, 2 * i + 1\n",
    "        stack.pop()\n",
    "        while stack:\n",
    "            s, t, i = stack.pop()\n",
    "            self.push_up(i, s, t)\n",
    "        assert i == 1\n",
    "        return self.ma[i]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeating(self, s: str, queryCharacters: str, queryIndices: List[int]) -> List[int]:\n",
    "        n = len(s)\n",
    "        tree = SegmentTreeLongestSubSame(n, [ord(w) - ord(\"a\") for w in s])\n",
    "        ans = []\n",
    "        for i, w in zip(queryIndices, queryCharacters):\n",
    "            ans.append(tree.update_point(i, i, 0, n - 1, ord(w) - ord(\"a\"), 1))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SegmentTreeLongestSubSame:\n",
    "    # 模板：单点字母更新，最长具有相同字母的连续子数组查询\n",
    "    def __init__(self, n, lst):\n",
    "        self.n = n\n",
    "        self.lst = lst\n",
    "        # 注意深浅拷贝的问题\n",
    "        self.pref = [0]*4*n\n",
    "        self.suf = [0]*4*n\n",
    "        self.ma = [0]*4*n\n",
    "        self.build()\n",
    "        return\n",
    "\n",
    "    def build(self):\n",
    "        # 使用数组初始化线段树\n",
    "        stack = [[0, self.n - 1, 1]]\n",
    "        while stack:\n",
    "            s, t, ind = stack.pop()\n",
    "            if ind >= 0:\n",
    "                if s == t:\n",
    "                    self.make_tag(ind)\n",
    "                else:\n",
    "                    stack.append([s, t, ~ind])\n",
    "                    m = s + (t - s) // 2\n",
    "                    stack.append([s, m, 2 * ind])\n",
    "                    stack.append([m + 1, t, 2 * ind + 1])\n",
    "            else:\n",
    "                ind = ~ind\n",
    "                self.push_up(ind, s, t)\n",
    "        return\n",
    "\n",
    "    def make_tag(self, i):\n",
    "        self.pref[i] = 1\n",
    "        self.suf[i] = 1\n",
    "        self.ma[i] = 1\n",
    "        return\n",
    "\n",
    "    def push_up(self, i, s, t):\n",
    "        m = s + (t - s) // 2\n",
    "        # [s, m] 与 [m+1, t]\n",
    "        self.pref[i] = self.pref[2*i]\n",
    "        if self.pref[2*i] == m - s + 1 and self.lst[m] == self.lst[m+1]:\n",
    "            self.pref[i] += self.pref[2*i+1]\n",
    "\n",
    "        self.suf[i] = self.suf[2 * i + 1]\n",
    "        if self.suf[2 * i + 1] == t - m and self.lst[m] == self.lst[m + 1]:\n",
    "            self.suf[i] += self.suf[2 * i]\n",
    "        \n",
    "\n",
    "        ma1 = max(self.pref[i], self.suf[i])\n",
    "        if self.lst[m] == self.lst[m+1]:\n",
    "            ma1 = max(ma1, self.suf[2*i]+self.pref[2*i+1])\n",
    "        ma2 = max(self.ma[2*i], self.ma[2*i+1])\n",
    "        self.ma[i] = max(ma1, ma2)\n",
    "        return\n",
    "\n",
    "    def update_point(self, left, right, s, t, val, i):\n",
    "        # 更新单点最小值\n",
    "        self.lst[left] = val\n",
    "        stack = []\n",
    "        while True:\n",
    "            stack.append([s, t, i])\n",
    "            if s == t:\n",
    "                self.make_tag(i)\n",
    "                break\n",
    "            m = s + (t - s) // 2\n",
    "            if left <= m:  # 注意左右子树的边界与范围\n",
    "                s, t, i = s, m, 2 * i\n",
    "            if right > m:\n",
    "                s, t, i = m + 1, t, 2 * i + 1\n",
    "        stack.pop()\n",
    "        while stack:\n",
    "            s, t, i = stack.pop()\n",
    "            self.push_up(i, s, t)\n",
    "        assert i == 1\n",
    "        return self.ma[i]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeating(self, s: str, queryCharacters: str, queryIndices: List[int]) -> List[int]:\n",
    "        n = len(s)\n",
    "        tree = SegmentTreeLongestSubSame(n, [ord(w) - ord(\"a\") for w in s])\n",
    "        ans = []\n",
    "        for i, w in zip(queryIndices, queryCharacters):\n",
    "            ans.append(tree.update_point(i, i, 0, n - 1, ord(w) - ord(\"a\"), 1))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeating(self, s: str, queryCharacters: str, queryIndices: List[int]) -> List[int]:\n",
    "        \n",
    "\n",
    "\n",
    "        def build():\n",
    "            # 使用数组初始化线段树\n",
    "            stack = [[0, n - 1, 1]]\n",
    "            while stack:\n",
    "                s, t, ind = stack.pop()\n",
    "                if ind >= 0:\n",
    "                    if s == t:\n",
    "                        make_tag(ind)\n",
    "                    else:\n",
    "                        stack.append([s, t, ~ind])\n",
    "                        m = s + (t - s) // 2\n",
    "                        stack.append([s, m, 2 * ind])\n",
    "                        stack.append([m + 1, t, 2 * ind + 1])\n",
    "                else:\n",
    "                    ind = ~ind\n",
    "                    push_up(ind, s, t)\n",
    "            return\n",
    "    \n",
    "        def make_tag(i):\n",
    "            # 只有此时 i 对应的区间 s==t 才打标记\n",
    "            pref[i] = 1\n",
    "            suf[i] = 1\n",
    "            ceil[i] = 1\n",
    "            return\n",
    "    \n",
    "        def push_up(i, s, t):\n",
    "            m = s + (t - s) // 2\n",
    "            # 左右区间段分别为 [s, m] 与 [m+1, t] 保证 s < t\n",
    "            pref[i] = pref[2 * i]\n",
    "            if pref[2 * i] == m - s + 1 and lst[m] == lst[m + 1]:\n",
    "                pref[i] += pref[2 * i + 1]\n",
    "    \n",
    "            suf[i] = suf[2 * i + 1]\n",
    "            if suf[2 * i + 1] == t - m and lst[m] == lst[m + 1]:\n",
    "                suf[i] += suf[2 * i]\n",
    "    \n",
    "            a = -inf\n",
    "            for b in [pref[i], suf[i], ceil[2 * i], ceil[2 * i + 1]]:\n",
    "                a = a if a > b else b\n",
    "            if lst[m] == lst[m + 1]:\n",
    "                b = suf[2 * i] + pref[2 * i + 1]\n",
    "                a = a if a > b else b\n",
    "            ceil[i] = a\n",
    "            return\n",
    "    \n",
    "        def update_point(left, right, s, t, val, i):\n",
    "            # 更新单点最小值\n",
    "            lst[left] = val\n",
    "            stack = []\n",
    "            while True:\n",
    "                stack.append([s, t, i])\n",
    "                if left <= s <= t <= right:\n",
    "                    make_tag(i)\n",
    "                    break\n",
    "                m = s + (t - s) // 2\n",
    "                if left <= m:  # 注意左右子树的边界与范围\n",
    "                    s, t, i = s, m, 2 * i\n",
    "                if right > m:\n",
    "                    s, t, i = m + 1, t, 2 * i + 1\n",
    "            stack.pop()\n",
    "            while stack:\n",
    "                s, t, i = stack.pop()\n",
    "                push_up(i, s, t)\n",
    "            assert i == 1\n",
    "            # 获取当前最大的连续子串\n",
    "            return ceil[1]\n",
    "\n",
    "        n = len(s)\n",
    "        lst = [ord(w) - ord(\"a\") for w in s]\n",
    "        pref = [0] * 4 * n\n",
    "        suf = [0] * 4 * n\n",
    "        ceil = [0] * 4 * n\n",
    "        build()\n",
    "        ans = []\n",
    "        for index, w in zip(queryIndices, queryCharacters):\n",
    "            ans.append(update_point(index, index, 0, n - 1, ord(w) - ord(\"a\"), 1))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "# sys.set_int_max_str_digits(0)  # 大数的范围坑\n",
    "\n",
    "\n",
    "def ac_max(a, b):\n",
    "    return a if a > b else b\n",
    "\n",
    "\n",
    "def ac_min(a, b):\n",
    "    return a if a < b else b\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeating(self, s: str, queryCharacters: str, queryIndices: List[int]) -> List[int]:\n",
    "        lst = SortedList()\n",
    "        s = list(s)\n",
    "        n = len(s)\n",
    "        pre = s[0]\n",
    "        cnt = 1\n",
    "        length = SortedList()\n",
    "        for i in range(1, n):\n",
    "            if s[i] == pre:\n",
    "                cnt += 1\n",
    "            else:\n",
    "                lst.add([i - cnt, i - 1])\n",
    "                length.add(cnt)\n",
    "                cnt = 1\n",
    "                pre = s[i]\n",
    "        lst.add([n - cnt, n - 1])\n",
    "        length.add(cnt)\n",
    "        ans = []\n",
    "\n",
    "        def find(target_ind):\n",
    "            ii = lst.bisect_left([target_ind, target_ind])\n",
    "            for xx in [ii - 1, ii, ii + 1]:\n",
    "                if 0 <= xx < len(lst) and lst[xx][0] <= target_ind <= lst[xx][1]:\n",
    "                    return xx\n",
    "\n",
    "        for ind, w in zip(queryIndices, queryCharacters):\n",
    "            if s[ind] == w:\n",
    "                ans.append(length[-1])\n",
    "                continue\n",
    "            s[ind] = w\n",
    "\n",
    "            j = find(ind)\n",
    "            x, y = lst[j]\n",
    "            if x < ind < y:\n",
    "                lst.pop(j)\n",
    "                length.discard(y - x + 1)\n",
    "\n",
    "                lst.add([ind, ind])\n",
    "                length.add(1)\n",
    "\n",
    "                lst.add([x, ind - 1])\n",
    "                length.add(ind - x)\n",
    "\n",
    "                lst.add([ind + 1, y])\n",
    "                length.add(y - ind)\n",
    "\n",
    "            elif x == ind < y:\n",
    "                lst.pop(j)\n",
    "                length.discard(y - x + 1)\n",
    "\n",
    "                lst.add([ind + 1, y])\n",
    "                length.add(y - ind)\n",
    "\n",
    "                if not x or s[x - 1] != s[x]:\n",
    "                    lst.add([x, x])\n",
    "                    length.add(1)\n",
    "                else:\n",
    "                    j = find(x-1)\n",
    "                    a, b = lst.pop(j)\n",
    "                    length.discard(b - a + 1)\n",
    "\n",
    "                    lst.add([a, ind])\n",
    "                    length.add(ind - a + 1)\n",
    "\n",
    "            elif x < y == ind:\n",
    "                lst.pop(j)\n",
    "                length.discard(y - x + 1)\n",
    "                lst.add([x, ind - 1])\n",
    "                length.add(ind - x)\n",
    "                if ind == n - 1 or s[ind + 1] != s[ind]:\n",
    "                    lst.add([ind, ind])\n",
    "                    length.add(1)\n",
    "                else:\n",
    "                    j = find(ind+1)\n",
    "                    a, b = lst.pop(j)\n",
    "                    length.discard(b - a + 1)\n",
    "\n",
    "                    lst.add([ind, b])\n",
    "                    length.add(b - ind + 1)\n",
    "\n",
    "            else:  # x=y=ind\n",
    "                lst.pop(j)\n",
    "                length.discard(1)\n",
    "\n",
    "                if not x or s[x - 1] != s[ind]:\n",
    "                    lst.add([x, x])\n",
    "                    length.add(1)\n",
    "                    a, b = x, x\n",
    "                else:\n",
    "                    j = find(x-1)\n",
    "                    a, b = lst.pop(j)\n",
    "                    length.discard(b - a + 1)\n",
    "\n",
    "                    lst.add([a, ind])\n",
    "                    length.add(ind - a + 1)\n",
    "                    a, b = a, ind\n",
    "\n",
    "                if not (ind == n - 1 or s[ind + 1] != s[ind]):\n",
    "                    j = find(ind + 1)\n",
    "                    c, d = lst.pop(j)\n",
    "                    length.discard(d - c + 1)\n",
    "\n",
    "                    lst.discard([a, b])\n",
    "                    length.discard(b - a + 1)\n",
    "\n",
    "                    lst.add([a, d])\n",
    "                    length.add(d - a + 1)\n",
    "\n",
    "            ans.append(length[-1])\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import *\n",
    "class Solution:\n",
    "    def longestRepeating(self, s: str, queryCharacters: str, queryIndices: List[int]) -> List[int]:\n",
    "        n = len(s)\n",
    "        s = list(s)\n",
    "        dic = {}\n",
    "        begin = SortedList()\n",
    "        st = SortedList()\n",
    "\n",
    "        idx = 0\n",
    "        while idx < n:\n",
    "            ch = s[idx]\n",
    "            l = idx\n",
    "            while idx < n and s[idx] == ch:\n",
    "                idx += 1\n",
    "            t = (idx - l, l, idx - 1)\n",
    "            dic[l] = t\n",
    "            begin.add(l)\n",
    "            st.add(t)\n",
    "\n",
    "        ans = []\n",
    "        for i, q in enumerate(queryIndices):\n",
    "            if s[q] == queryCharacters[i]:\n",
    "                ans.append(st[-1][0])\n",
    "                continue\n",
    "\n",
    "            s[q] = queryCharacters[i]\n",
    "            idx = begin.bisect_right(q)\n",
    "            l = begin[idx - 1]\n",
    "            t = dic[l]\n",
    "            _, l, r = t\n",
    "            del dic[l]\n",
    "            begin.remove(l)\n",
    "            st.remove(t)\n",
    "\n",
    "            # 添加可能新产生的左右区间\n",
    "            if q - 1 >= l:\n",
    "                t1 = (q - l, l, q - 1)\n",
    "                dic[l] = t1\n",
    "                begin.add(l)\n",
    "                st.add(t1)\n",
    "            if q + 1 <= r:\n",
    "                t2 = (r - q, q + 1, r)\n",
    "                dic[q + 1] = t2\n",
    "                begin.add(q + 1)\n",
    "                st.add(t2)\n",
    "\n",
    "            # 检查左右区间\n",
    "            res = [[q, q]]\n",
    "            if q > 0 and s[q] == s[q - 1]:\n",
    "                idx1 = begin.bisect_right(q - 1)\n",
    "                l1 = begin[idx1 - 1]\n",
    "                t1 = dic[l1]\n",
    "                del dic[l1]\n",
    "                begin.remove(l1)\n",
    "                st.remove(t1)\n",
    "                res.append([t1[1], t1[2]])\n",
    "            if q != n - 1 and s[q] == s[q + 1]:\n",
    "                idx2 = begin.bisect_right(q + 1)\n",
    "                l2 = begin[idx2 - 1]\n",
    "                t2 = dic[l2]\n",
    "                del dic[l2]\n",
    "                begin.remove(l2)\n",
    "                st.remove(t2)\n",
    "                res.append([t2[1], t2[2]])\n",
    "\n",
    "            # 合并区间\n",
    "            l, r = min(x[0] for x in res), max(x[1] for x in res)\n",
    "            t = (r - l + 1, l, r)\n",
    "            dic[l] = t\n",
    "            begin.add(l)\n",
    "            st.add(t)\n",
    "\n",
    "            ans.append(st[-1][0])\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from typing import List\n",
    "from sortedcontainers import SortedList\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class LenControl:\n",
    "    def __init__(self):\n",
    "        self.sd1 = SortedList(key=lambda x: (x[0], x[1]))\n",
    "        self.top = SortedList(key=lambda x: -x)\n",
    "\n",
    "    def addElement(self, val):\n",
    "        if len(self.sd1) == 0:\n",
    "            self.sd1.add((val, val))\n",
    "            self.top.add(1)\n",
    "        else:\n",
    "            idx1 = self.sd1.bisect_left((val, val))\n",
    "            if idx1 == 0:\n",
    "                v1 = self.sd1[idx1]\n",
    "                range1 = v1[1] - v1[0] + 1\n",
    "                if v1[0] - 1 == val:\n",
    "                    self.top.remove(range1)\n",
    "                    self.top.add(range1 + 1)\n",
    "                    self.sd1.remove(v1)\n",
    "                    self.sd1.add((v1[0] - 1, v1[1]))\n",
    "                else:\n",
    "                    self.top.add(1)\n",
    "                    self.sd1.add((val, val))\n",
    "            elif idx1 == len(self.sd1):\n",
    "                v1 = self.sd1[idx1 - 1]\n",
    "                range1 = v1[1] - v1[0] + 1\n",
    "                if v1[1] + 1 == val:\n",
    "                    self.top.remove(range1)\n",
    "                    self.top.add(range1 + 1)\n",
    "                    self.sd1.remove(v1)\n",
    "                    self.sd1.add((v1[0], v1[1] + 1))\n",
    "                else:\n",
    "                    self.top.add(1)\n",
    "                    self.sd1.add((val, val))\n",
    "            else:\n",
    "                leftval = self.sd1[idx1 - 1]\n",
    "                rightval = self.sd1[idx1]\n",
    "                range_l = leftval[1] - leftval[0] + 1\n",
    "                range_r = rightval[1] - rightval[0] + 1\n",
    "                if leftval[1] + 1 == val and rightval[0] - 1 == val:\n",
    "                    self.top.remove(range_l)\n",
    "                    self.top.remove(range_r)\n",
    "                    self.top.add(range_r + range_l + 1)\n",
    "                    self.sd1.remove(leftval)\n",
    "                    self.sd1.remove(rightval)\n",
    "                    self.sd1.add((leftval[0], rightval[1]))\n",
    "                elif leftval[1] + 1 == val:\n",
    "                    self.top.remove(range_l)\n",
    "                    self.top.add(range_l + 1)\n",
    "                    self.sd1.remove(leftval)\n",
    "                    self.sd1.add((leftval[0], val))\n",
    "                elif rightval[0] - 1 == val:\n",
    "                    self.top.remove(range_r)\n",
    "                    self.top.add(range_r + 1)\n",
    "                    self.sd1.remove(rightval)\n",
    "                    self.sd1.add((val, rightval[1]))\n",
    "                else:\n",
    "                    self.top.add(1)\n",
    "                    self.sd1.add((val, val))\n",
    "\n",
    "    def removeElement(self, val):\n",
    "        idx1 = self.sd1.bisect_left((val, math.inf))\n",
    "        valx = self.sd1[idx1 - 1]\n",
    "        rang1 = valx[1] - valx[0] + 1\n",
    "        if rang1 == 1:\n",
    "            self.top.remove(1)\n",
    "            self.sd1.remove(valx)\n",
    "        else:\n",
    "            self.top.remove(rang1)\n",
    "            self.sd1.remove(valx)\n",
    "            leftp = val - 1 - valx[0]\n",
    "            if leftp >= 0:\n",
    "                self.top.add(leftp + 1)\n",
    "                self.sd1.add((valx[0], val - 1))\n",
    "            rightp = valx[1] - 1 - val\n",
    "            if rightp >= 0:\n",
    "                self.top.add(rightp + 1)\n",
    "                self.sd1.add((val + 1, valx[1]))\n",
    "\n",
    "    def getMost(self):\n",
    "        if len(self.top) > 0:\n",
    "            return self.top[0]\n",
    "        return 0\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeating(self, s: str, queryCharacters: str, queryIndices: List[int]) -> List[int]:\n",
    "        \"\"\"\n",
    "\n",
    "        :param s:\n",
    "        :param queryCharacters:\n",
    "        :param queryIndices:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        mm = defaultdict(LenControl)\n",
    "        for k, v in enumerate(s):\n",
    "            if v not in mm:\n",
    "                lc = LenControl()\n",
    "                lc.addElement(k)\n",
    "                mm[v] = lc\n",
    "            else:\n",
    "                mm[v].addElement(k)\n",
    "        cur_max = 0\n",
    "        for i in mm:\n",
    "            cur_max = max(cur_max, mm[i].top[0])\n",
    "        ret = []\n",
    "        clist = [i for i in s]\n",
    "        for i in zip(queryCharacters, queryIndices):\n",
    "\n",
    "            char_to_rep = i[0]\n",
    "            char_idx = i[1]\n",
    "            chars = clist[char_idx]\n",
    "            toadd_lc, to_remove_lc = mm[char_to_rep], mm[chars]\n",
    "            if char_to_rep == chars:\n",
    "                ret.append(cur_max)\n",
    "            else:\n",
    "                toadd_lc.addElement(char_idx)\n",
    "                to_remove_lc.removeElement(char_idx)\n",
    "                cur_max = 0\n",
    "                for j in mm:\n",
    "                    cur_max = max(cur_max, mm[j].getMost())\n",
    "                ret.append(cur_max)\n",
    "            clist[char_idx] = char_to_rep\n",
    "\n",
    "        return ret\n",
    "\n",
    "\n",
    "a = Solution()\n",
    "print(a.longestRepeating(s=\"geuqjmt\", queryCharacters=\"bgemoegklm\", queryIndices=[3, 4, 2, 6, 5, 6, 5, 4, 3, 2]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from typing import List\n",
    "from sortedcontainers import SortedList\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class LenControl:\n",
    "    def __init__(self):\n",
    "        self.sd1 = SortedList(key=lambda x: (x[0], x[1]))\n",
    "        self.top = SortedList(key=lambda x: -x)\n",
    "\n",
    "    def addElement(self, val):\n",
    "        if len(self.sd1) == 0:\n",
    "            self.sd1.add((val, val))\n",
    "            self.top.add(1)\n",
    "        else:\n",
    "            idx1 = self.sd1.bisect_left((val, val))\n",
    "            if idx1 == 0:\n",
    "                v1 = self.sd1[idx1]\n",
    "                range1 = v1[1] - v1[0] + 1\n",
    "                if v1[0] - 1 == val:\n",
    "                    self.top.remove(range1)\n",
    "                    self.top.add(range1 + 1)\n",
    "                    self.sd1.remove(v1)\n",
    "                    self.sd1.add((v1[0] - 1, v1[1]))\n",
    "                else:\n",
    "                    self.top.add(1)\n",
    "                    self.sd1.add((val, val))\n",
    "            elif idx1 == len(self.sd1):\n",
    "                v1 = self.sd1[idx1 - 1]\n",
    "                range1 = v1[1] - v1[0] + 1\n",
    "                if v1[1] + 1 == val:\n",
    "                    self.top.remove(range1)\n",
    "                    self.top.add(range1 + 1)\n",
    "                    self.sd1.remove(v1)\n",
    "                    self.sd1.add((v1[0], v1[1] + 1))\n",
    "                else:\n",
    "                    self.top.add(1)\n",
    "                    self.sd1.add((val, val))\n",
    "            else:\n",
    "                leftval = self.sd1[idx1 - 1]\n",
    "                rightval = self.sd1[idx1]\n",
    "                range_l = leftval[1] - leftval[0] + 1\n",
    "                range_r = rightval[1] - rightval[0] + 1\n",
    "                if leftval[1] + 1 == val and rightval[0] - 1 == val:\n",
    "                    self.top.remove(range_l)\n",
    "                    self.top.remove(range_r)\n",
    "                    self.top.add(range_r + range_l + 1)\n",
    "                    self.sd1.remove(leftval)\n",
    "                    self.sd1.remove(rightval)\n",
    "                    self.sd1.add((leftval[0], rightval[1]))\n",
    "                elif leftval[1] + 1 == val:\n",
    "                    self.top.remove(range_l)\n",
    "                    self.top.add(range_l + 1)\n",
    "                    self.sd1.remove(leftval)\n",
    "                    self.sd1.add((leftval[0], val))\n",
    "                elif rightval[0] - 1 == val:\n",
    "                    self.top.remove(range_r)\n",
    "                    self.top.add(range_r + 1)\n",
    "                    self.sd1.remove(rightval)\n",
    "                    self.sd1.add((val, rightval[1]))\n",
    "                else:\n",
    "                    self.top.add(1)\n",
    "                    self.sd1.add((val, val))\n",
    "\n",
    "    def removeElement(self, val):\n",
    "        idx1 = self.sd1.bisect_left((val, math.inf))\n",
    "        valx = self.sd1[idx1 - 1]\n",
    "        rang1 = valx[1] - valx[0] + 1\n",
    "        if rang1 == 1:\n",
    "            self.top.remove(1)\n",
    "            self.sd1.remove(valx)\n",
    "        else:\n",
    "            self.top.remove(rang1)\n",
    "            self.sd1.remove(valx)\n",
    "            leftp = val - 1 - valx[0]\n",
    "            if leftp >= 0:\n",
    "                self.top.add(leftp + 1)\n",
    "                self.sd1.add((valx[0], val - 1))\n",
    "            rightp = valx[1] - 1 - val\n",
    "            if rightp >= 0:\n",
    "                self.top.add(rightp + 1)\n",
    "                self.sd1.add((val + 1, valx[1]))\n",
    "\n",
    "    def getMost(self):\n",
    "        if len(self.top) > 0:\n",
    "            return self.top[0]\n",
    "        return 0\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeating(self, s: str, queryCharacters: str, queryIndices: List[int]) -> List[int]:\n",
    "        \"\"\"\n",
    "\n",
    "        :param s:\n",
    "        :param queryCharacters:\n",
    "        :param queryIndices:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        mm = defaultdict(LenControl)\n",
    "        for k, v in enumerate(s):\n",
    "            if v not in mm:\n",
    "                lc = LenControl()\n",
    "                lc.addElement(k)\n",
    "                mm[v] = lc\n",
    "            else:\n",
    "                mm[v].addElement(k)\n",
    "        cur_max = 0\n",
    "        for i in mm:\n",
    "            cur_max = max(cur_max, mm[i].top[0])\n",
    "        ret = []\n",
    "        clist = [i for i in s]\n",
    "        for i in zip(queryCharacters, queryIndices):\n",
    "\n",
    "            char_to_rep = i[0]\n",
    "            char_idx = i[1]\n",
    "            chars = clist[char_idx]\n",
    "            toadd_lc, to_remove_lc = mm[char_to_rep], mm[chars]\n",
    "            if char_to_rep == chars:\n",
    "                ret.append(cur_max)\n",
    "            else:\n",
    "                toadd_lc.addElement(char_idx)\n",
    "                to_remove_lc.removeElement(char_idx)\n",
    "                cur_max = 0\n",
    "                for j in mm:\n",
    "                    cur_max = max(cur_max, mm[j].getMost())\n",
    "                ret.append(cur_max)\n",
    "            clist[char_idx] = char_to_rep\n",
    "\n",
    "        return ret\n",
    "\n",
    "\n",
    "a = Solution()\n",
    "print(a.longestRepeating(s=\"geuqjmt\", queryCharacters=\"bgemoegklm\", queryIndices=[3, 4, 2, 6, 5, 6, 5, 4, 3, 2]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import *\n",
    "class Solution:\n",
    "    def longestRepeating(self, s: str, queryCharacters: str, queryIndices: List[int]) -> List[int]:\n",
    "        n = len(s)\n",
    "        ss = list(s)\n",
    "        st = SortedList()\n",
    "        begin = SortedList()\n",
    "        dic = {}\n",
    "\n",
    "        idx = 0\n",
    "        while idx < n:\n",
    "            ch = s[idx]\n",
    "            l = idx\n",
    "            while idx < n and s[idx] == ch:\n",
    "                idx += 1\n",
    "            begin.add(l)\n",
    "            t = (idx - l, l, idx - 1, ch)\n",
    "            dic[l] = t\n",
    "            st.add(t)\n",
    "        \n",
    "        ans = []\n",
    "        for i, q in enumerate(queryIndices):\n",
    "            if ss[q] == queryCharacters[i]:\n",
    "                ans.append(st[-1][0])\n",
    "                continue\n",
    "\n",
    "            ss[q] = queryCharacters[i]\n",
    "            idx = begin.bisect_right(q)\n",
    "            l = begin[idx - 1]\n",
    "            t = dic[l]\n",
    "            lt, l, r, ch = t\n",
    "\n",
    "            del dic[l]\n",
    "            begin.remove(l)\n",
    "            st.remove(t)\n",
    "            \n",
    "            if q == l:\n",
    "                if lt > 1:\n",
    "                    t1 = (lt - 1, l + 1, r, ch)\n",
    "                    begin.add(l + 1)\n",
    "                    dic[l + 1] = t1\n",
    "                    st.add(t1)\n",
    "\n",
    "                # 检查左右区间\n",
    "                res = [[q, q]]\n",
    "                if q > 0 and ss[q] == ss[q - 1]:\n",
    "                    idx2 = begin.bisect_right(q - 1)\n",
    "                    l2 = begin[idx2 - 1]\n",
    "                    t2 = dic[l2]\n",
    "\n",
    "                    del dic[l2]\n",
    "                    begin.remove(l2)\n",
    "                    st.remove(t2)\n",
    "                    res.append([t2[1], t2[2]])\n",
    "\n",
    "                if q != n - 1 and ss[q] == ss[q + 1]:\n",
    "                    idx3 = begin.bisect_right(q + 1)\n",
    "                    l3 = begin[idx3 - 1]\n",
    "                    t3 = dic[l3]\n",
    "\n",
    "                    del dic[l3]\n",
    "                    st.remove(t3)\n",
    "                    begin.remove(l3)\n",
    "                    res.append([t3[1], t3[2]])\n",
    "\n",
    "                l, r = min(x[0] for x in res), max(x[1] for x in res)\n",
    "                t = (r - l + 1, l, r, ss[q])\n",
    "                begin.add(l)\n",
    "                dic[l] = t\n",
    "                st.add(t)\n",
    "            elif q == r:\n",
    "                if lt > 1:\n",
    "                    t1 = (lt - 1, l, q - 1, ch)\n",
    "                    begin.add(l)\n",
    "                    dic[l] = t1\n",
    "                    st.add(t1)\n",
    "\n",
    "                # 检查左右区间\n",
    "                res = [[q, q]]\n",
    "                if q > 0 and ss[q] == ss[q - 1]:\n",
    "                    idx2 = begin.bisect_right(q - 1)\n",
    "                    l2 = begin[idx2 - 1]\n",
    "                    t2 = dic[l2]\n",
    "\n",
    "                    del dic[l2]\n",
    "                    begin.remove(l2)\n",
    "                    st.remove(t2)\n",
    "                    res.append([t2[1], t2[2]])\n",
    "                if q != n - 1 and ss[q] == ss[q + 1]:\n",
    "                    idx3 = begin.bisect_right(q + 1)\n",
    "                    l3 = begin[idx3 - 1]\n",
    "                    t3 = dic[l3]\n",
    "\n",
    "                    del dic[l3]\n",
    "                    begin.remove(l3)\n",
    "                    st.remove(t3)\n",
    "                    res.append([t3[1], t3[2]])\n",
    "\n",
    "                l, r = min(x[0] for x in res), max(x[1] for x in res)\n",
    "                t = (r - l + 1, l, r, ss[q])\n",
    "                begin.add(l)\n",
    "                dic[l] = t\n",
    "                st.add(t)\n",
    "            else:\n",
    "                t1 = (q - l, l, q - 1, ch)\n",
    "                dic[l] = t1\n",
    "                begin.add(l)\n",
    "                st.add(t1)\n",
    "\n",
    "                t2 = (r - q, q + 1, r, ch)\n",
    "                begin.add(q + 1)\n",
    "                dic[q + 1] = t2\n",
    "                st.add(t2)\n",
    "\n",
    "                t3 = (1, q, q, ss[q])\n",
    "                begin.add(q)\n",
    "                dic[q] = t3\n",
    "                st.add(t3)\n",
    "\n",
    "            ans.append(st[-1][0])\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import *\n",
    "class Solution:\n",
    "    def longestRepeating(self, s: str, queryCharacters: str, queryIndices: List[int]) -> List[int]:\n",
    "        n = len(s)\n",
    "        ss = list(s)\n",
    "        st = SortedList()\n",
    "        begin = SortedList()\n",
    "        dic = {}\n",
    "\n",
    "        idx = 0\n",
    "        while idx < n:\n",
    "            ch = s[idx]\n",
    "            l = idx\n",
    "            while idx < n and s[idx] == ch:\n",
    "                idx += 1\n",
    "            begin.add(l)\n",
    "            t = (idx - l, l, idx - 1, ch)\n",
    "            dic[l] = t\n",
    "            st.add(t)\n",
    "\n",
    "        ans = []\n",
    "        for i, q in enumerate(queryIndices):\n",
    "            if ss[q] == queryCharacters[i]:\n",
    "                ans.append(st[-1][0])\n",
    "                continue\n",
    "\n",
    "            ss[q] = queryCharacters[i]\n",
    "            idx = begin.bisect_right(q)\n",
    "            l = begin[idx - 1]\n",
    "            t = dic[l]\n",
    "            lt, l, r, ch = t\n",
    "            del dic[l]\n",
    "            begin.remove(l)\n",
    "            st.remove(t)\n",
    "\n",
    "            if q == l:\n",
    "                if lt > 1:\n",
    "                    t1 = (lt - 1, l + 1, r, ch)\n",
    "                    begin.add(l + 1)\n",
    "                    dic[l + 1] = t1\n",
    "                    st.add(t1)\n",
    "            elif q == r:\n",
    "                if lt > 1:\n",
    "                    t1 = (lt - 1, l, q - 1, ch)\n",
    "                    begin.add(l)\n",
    "                    dic[l] = t1\n",
    "                    st.add(t1)\n",
    "            else:\n",
    "                t1 = (q - l, l, q - 1, ch)\n",
    "                dic[l] = t1\n",
    "                begin.add(l)\n",
    "                st.add(t1)\n",
    "\n",
    "                t2 = (r - q, q + 1, r, ch)\n",
    "                begin.add(q + 1)\n",
    "                dic[q + 1] = t2\n",
    "                st.add(t2)\n",
    "\n",
    "            # 检查左右区间\n",
    "            res = [[q, q]]\n",
    "            if q > 0 and ss[q] == ss[q - 1]:\n",
    "                idx2 = begin.bisect_right(q - 1)\n",
    "                l2 = begin[idx2 - 1]\n",
    "                t2 = dic[l2]\n",
    "                del dic[l2]\n",
    "                begin.remove(l2)\n",
    "                st.remove(t2)\n",
    "                res.append([t2[1], t2[2]])\n",
    "            if q != n - 1 and ss[q] == ss[q + 1]:\n",
    "                idx3 = begin.bisect_right(q + 1)\n",
    "                l3 = begin[idx3 - 1]\n",
    "                t3 = dic[l3]\n",
    "                del dic[l3]\n",
    "                st.remove(t3)\n",
    "                begin.remove(l3)\n",
    "                res.append([t3[1], t3[2]])\n",
    "\n",
    "            l, r = min(x[0] for x in res), max(x[1] for x in res)\n",
    "            t = (r - l + 1, l, r, ss[q])\n",
    "            begin.add(l)\n",
    "            dic[l] = t\n",
    "            st.add(t)\n",
    "\n",
    "            ans.append(st[-1][0])\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, start, end):\n",
    "        self.start = start\n",
    "        self.end = end \n",
    "        self.left = None \n",
    "        self.right = None \n",
    "        self.tolLen = 1\n",
    "        self.rightLen = 1\n",
    "        self.leftLen = 1\n",
    "\n",
    "class SegmentTree:\n",
    "    def __init__(self, array):\n",
    "        n = len(array)\n",
    "        self.array = list(array)\n",
    "        self.root = self.build(0, n - 1)\n",
    "    \n",
    "    def build(self, start, end):\n",
    "        if start > end:\n",
    "            return None \n",
    "        root = Node(start, end)\n",
    "        if start == end:\n",
    "            return root \n",
    "        mid = start + (end - start) // 2 \n",
    "        root.left = self.build(start, mid)\n",
    "        root.right = self.build(mid + 1, end)\n",
    "        self.push_up(root)\n",
    "        return root \n",
    "    \n",
    "    def update(self, root, idx, c):\n",
    "        if root.start == root.end:\n",
    "            self.array[idx] = c \n",
    "        else:\n",
    "            mid = root.start + (root.end - root.start) // 2 \n",
    "            if idx <= mid:\n",
    "                self.update(root.left, idx, c)\n",
    "            else:\n",
    "                self.update(root.right, idx, c)\n",
    "        self.push_up(root)\n",
    "    \n",
    "    def push_up(self, root):\n",
    "        if root.start == root.end:\n",
    "            return \n",
    "        mid = root.start + (root.end - root.start) // 2 \n",
    "        root.leftLen = root.left.leftLen\n",
    "        root.rightLen = root.right.rightLen\n",
    "        root.tolLen = max(root.left.tolLen, root.right.tolLen)\n",
    "        if self.array[mid] == self.array[mid + 1]:\n",
    "            root.tolLen = max(root.tolLen, root.left.rightLen + root.right.leftLen)\n",
    "            if root.left.leftLen == mid - root.start + 1:\n",
    "                root.leftLen += root.right.leftLen\n",
    "            if root.right.rightLen == root.end - mid:\n",
    "                root.rightLen += root.left.rightLen\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeating(self, s: str, queryCharacters: str, queryIndices: List[int]) -> List[int]:\n",
    "        sg = SegmentTree(s)\n",
    "        res = []\n",
    "        for idx, c in zip(queryIndices, queryCharacters):\n",
    "            sg.update(sg.root, idx, c)\n",
    "            res.append(sg.root.tolLen)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, start, end):\n",
    "        self.start = start\n",
    "        self.end = end \n",
    "        self.left = None \n",
    "        self.right = None \n",
    "        self.tolLen = 1\n",
    "        self.rightLen = 1\n",
    "        self.leftLen = 1\n",
    "\n",
    "class SegmentTree:\n",
    "    def __init__(self, array):\n",
    "        n = len(array)\n",
    "        self.array = list(array)\n",
    "        self.root = self.build(0, n - 1)\n",
    "    \n",
    "    def build(self, start, end):\n",
    "        if start > end:\n",
    "            return None \n",
    "        root = Node(start, end)\n",
    "        if start == end:\n",
    "            return root \n",
    "        mid = start + (end - start) // 2 \n",
    "        root.left = self.build(start, mid)\n",
    "        root.right = self.build(mid + 1, end)\n",
    "        self.push_up(root)\n",
    "        return root \n",
    "    \n",
    "    def update(self, root, idx, c):\n",
    "        if root.start == root.end:\n",
    "            self.array[idx] = c \n",
    "        else:\n",
    "            mid = root.start + (root.end - root.start) // 2 \n",
    "            if idx <= mid:\n",
    "                self.update(root.left, idx, c)\n",
    "            else:\n",
    "                self.update(root.right, idx, c)\n",
    "        self.push_up(root)\n",
    "    \n",
    "    def push_up(self, root):\n",
    "        if root.start == root.end:\n",
    "            return \n",
    "        mid = root.start + (root.end - root.start) // 2 \n",
    "        root.leftLen = root.left.leftLen\n",
    "        root.rightLen = root.right.rightLen\n",
    "        root.tolLen = max(root.left.tolLen, root.right.tolLen)\n",
    "        if self.array[mid] == self.array[mid + 1]:\n",
    "            root.tolLen = max(root.tolLen, root.left.rightLen + root.right.leftLen)\n",
    "            if root.left.leftLen == mid - root.start + 1:\n",
    "                root.leftLen += root.right.leftLen\n",
    "            if root.right.rightLen == root.end - mid:\n",
    "                root.rightLen += root.left.rightLen\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeating(self, s: str, queryCharacters: str, queryIndices: List[int]) -> List[int]:\n",
    "        sg = SegmentTree(s)\n",
    "        res = []\n",
    "        for idx, c in zip(queryIndices, queryCharacters):\n",
    "            sg.update(sg.root, idx, c)\n",
    "            res.append(sg.root.tolLen)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeating(self, s: str, queryCharacters: str, queryIndices: List[int]) -> List[int]:\n",
    "        s = list(s)\n",
    "        n = len(s)\n",
    "        pre = [0] * (4 * n)\n",
    "        suf = [0] * (4 * n)\n",
    "        mx = [0] * (4 * n)\n",
    "\n",
    "        def maintain(o: int, l: int, r: int) -> None:\n",
    "            pre[o] = pre[o * 2]\n",
    "            suf[o] = suf[o * 2 + 1]\n",
    "            mx[o] = max(mx[o * 2], mx[o * 2 + 1])\n",
    "            m = (l + r) // 2\n",
    "            if s[m - 1] == s[m]:  # 中间字符相同，可以合并\n",
    "                if suf[o * 2] == m - l + 1:\n",
    "                    pre[o] += pre[o * 2 + 1]\n",
    "                if pre[o * 2 + 1] == r - m:\n",
    "                    suf[o] += suf[o * 2]\n",
    "                mx[o] = max(mx[o], suf[o * 2] + pre[o * 2 + 1])\n",
    "\n",
    "        def build(o: int, l: int, r: int) -> None:\n",
    "            if l == r:\n",
    "                pre[o] = suf[o] = mx[o] = 1\n",
    "                return\n",
    "            m = (l + r) // 2\n",
    "            build(o * 2, l, m)\n",
    "            build(o * 2 + 1, m + 1, r)\n",
    "            maintain(o, l, r)\n",
    "\n",
    "        def update(o: int, l: int, r: int, i: int) -> None:\n",
    "            if l == r: return\n",
    "            m = (l + r) // 2\n",
    "            if i <= m:\n",
    "                update(o * 2, l, m, i)\n",
    "            else:\n",
    "                update(o * 2 + 1, m + 1, r, i)\n",
    "            maintain(o, l, r)\n",
    "\n",
    "        build(1, 1, n)\n",
    "        ans = []\n",
    "        for c, i in zip(queryCharacters, queryIndices):\n",
    "            s[i] = c\n",
    "            update(1, 1, n, i + 1)\n",
    "            ans.append(mx[1])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeating(self, s: str, queryCharacters: str, queryIndices: List[int]) -> List[int]:\n",
    "        s = list(s)\n",
    "        n = len(s)\n",
    "        pre = [0]*(4*n)\n",
    "        suf = [0]*(4*n)\n",
    "        mxc = [0]*(4*n)\n",
    "        def merge(t,l,r):\n",
    "            m = (l+r)>>1\n",
    "            pre[t] = pre[2*t]\n",
    "            suf[t] = suf[2*t+1]\n",
    "            mxc[t] = max(mxc[2*t], mxc[2*t+1])\n",
    "            if(s[m] == s[m+1]):\n",
    "                if(pre[2*t] == m-l+1):\n",
    "                    pre[t] = pre[2*t] + pre[2*t+1]\n",
    "                if(suf[2*t+1] == r - m):\n",
    "                    suf[t] = suf[2*t] + suf[2*t+1]\n",
    "                mxc[t] = max(mxc[t], suf[2*t]+pre[2*t+1])\n",
    "            return\n",
    "        \n",
    "        def build(t,l,r):\n",
    "            if(l == r):\n",
    "                pre[t] = 1\n",
    "                suf[t] = 1\n",
    "                mxc[t] = 1\n",
    "                return\n",
    "            m = (l+r)>>1\n",
    "            build(2*t,l,m)\n",
    "            build(2*t+1,m+1,r)\n",
    "            merge(t,l,r)\n",
    "            return\n",
    "        \n",
    "        def update(t,l,r,i):\n",
    "            if(l == r):\n",
    "                return \n",
    "            m = (l+r)>>1\n",
    "            if(i <= m):\n",
    "                update(2*t,l,m,i)\n",
    "            else:\n",
    "                update(2*t+1,m+1,r,i)\n",
    "            merge(t,l,r)\n",
    "            return\n",
    "\n",
    "        result = []\n",
    "        build(1,0,n-1)\n",
    "        for c,i in zip(queryCharacters, queryIndices):\n",
    "            s[i] = c \n",
    "            update(1,0,n-1,i)\n",
    "            result.append(mxc[1])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def longestRepeating(self, s: str, queryCharacters: str, queryIndices: List[int]) -> List[int]:\r\n",
    "        s = list(s)\r\n",
    "        n = len(s)\r\n",
    "        pre = [0] * (4 * n)\r\n",
    "        suf = [0] * (4 * n)\r\n",
    "        mx = [0] * (4 * n)\r\n",
    "\r\n",
    "        def maintain(o: int, l: int, r: int) -> None:\r\n",
    "            pre[o] = pre[o * 2]\r\n",
    "            suf[o] = suf[o * 2 + 1]\r\n",
    "            mx[o] = max(mx[o * 2], mx[o * 2 + 1])\r\n",
    "            m = (l + r) // 2\r\n",
    "            if s[m - 1] == s[m]:  # 中间字符相同，可以合并\r\n",
    "                if suf[o * 2] == m - l + 1:\r\n",
    "                    pre[o] += pre[o * 2 + 1]\r\n",
    "                if pre[o * 2 + 1] == r - m:\r\n",
    "                    suf[o] += suf[o * 2]\r\n",
    "                mx[o] = max(mx[o], suf[o * 2] + pre[o * 2 + 1])\r\n",
    "\r\n",
    "        def build(o: int, l: int, r: int) -> None:\r\n",
    "            if l == r:\r\n",
    "                pre[o] = suf[o] = mx[o] = 1\r\n",
    "                return\r\n",
    "            m = (l + r) // 2\r\n",
    "            build(o * 2, l, m)\r\n",
    "            build(o * 2 + 1, m + 1, r)\r\n",
    "            maintain(o, l, r)\r\n",
    "\r\n",
    "        def update(o: int, l: int, r: int, i: int) -> None:\r\n",
    "            if l == r: return\r\n",
    "            m = (l + r) // 2\r\n",
    "            if i <= m:\r\n",
    "                update(o * 2, l, m, i)\r\n",
    "            else:\r\n",
    "                update(o * 2 + 1, m + 1, r, i)\r\n",
    "            maintain(o, l, r)\r\n",
    "\r\n",
    "        build(1, 1, n)\r\n",
    "        ans = []\r\n",
    "        for c, i in zip(queryCharacters, queryIndices):\r\n",
    "            s[i] = c\r\n",
    "            update(1, 1, n, i + 1)\r\n",
    "            ans.append(mx[1])\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeating(self, s: str, queryCharacters: str, queryIndices: List[int]) -> List[int]:\n",
    "        s = list(s)\n",
    "        n = len(s)\n",
    "        pre = [0]*(4*n)\n",
    "        suf = [0]*(4*n)\n",
    "        mxc = [0]*(4*n)\n",
    "        def merge(t,l,r):\n",
    "            m = (l+r)>>1\n",
    "            pre[t] = pre[2*t]\n",
    "            suf[t] = suf[2*t+1]\n",
    "            mxc[t] = max(mxc[2*t], mxc[2*t+1])\n",
    "            if(s[m] == s[m+1]):\n",
    "                if(pre[2*t] == m-l+1):\n",
    "                    pre[t] = pre[2*t] + pre[2*t+1]\n",
    "                if(suf[2*t+1] == r - m):\n",
    "                    suf[t] = suf[2*t] + suf[2*t+1]\n",
    "                mxc[t] = max(mxc[t], suf[2*t]+pre[2*t+1])\n",
    "            return\n",
    "        \n",
    "        def build(t,l,r):\n",
    "            if(l == r):\n",
    "                pre[t] = 1\n",
    "                suf[t] = 1\n",
    "                mxc[t] = 1\n",
    "                return\n",
    "            m = (l+r)>>1\n",
    "            build(2*t,l,m)\n",
    "            build(2*t+1,m+1,r)\n",
    "            merge(t,l,r)\n",
    "            return\n",
    "        \n",
    "        def update(t,l,r,i):\n",
    "            if(l == r):\n",
    "                return \n",
    "            m = (l+r)>>1\n",
    "            if(i <= m):\n",
    "                update(2*t,l,m,i)\n",
    "            else:\n",
    "                update(2*t+1,m+1,r,i)\n",
    "            merge(t,l,r)\n",
    "            return\n",
    "\n",
    "        result = []\n",
    "        build(1,0,n-1)\n",
    "        for c,i in zip(queryCharacters, queryIndices):\n",
    "            s[i] = c \n",
    "            update(1,0,n-1,i)\n",
    "            result.append(mxc[1])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeating(self, s: str, queryCharacters: str, queryIndices: List[int]) -> List[int]:\n",
    "        s = list(s)\n",
    "        n = len(s)\n",
    "        pre, suf, mx = [[0] * (4 * n) for _ in range(3)]\n",
    "\n",
    "        def maintain(o, l, r):\n",
    "            pre[o] = pre[2 * o]\n",
    "            suf[o] = suf[2 * o + 1]\n",
    "            mx[o] = max(mx[2 * o], mx[2 * o + 1])\n",
    "            m = (l + r) // 2\n",
    "            if s[m - 1] == s[m]:\n",
    "                if suf[2 * o] == m - l + 1:\n",
    "                    pre[o] += pre[2 * o + 1]\n",
    "                if pre[2 * o + 1] == r - m:\n",
    "                    suf[o] += suf[2 * o]\n",
    "                mx[o] = max(mx[o], suf[2 * o] + pre[2 * o + 1])\n",
    "        \n",
    "        def build(o, l, r):\n",
    "            if l == r:\n",
    "                pre[o] = suf[o] = mx[o] = 1\n",
    "                return \n",
    "            m = (l + r) // 2\n",
    "            build(2 * o, l, m)\n",
    "            build(2 * o + 1, m + 1, r)\n",
    "            maintain(o, l, r)\n",
    "        \n",
    "        def update(o, l, r, i):\n",
    "            if l == r:\n",
    "                return \n",
    "            m = (l + r) // 2\n",
    "            if i <= m:\n",
    "                update(2 * o, l, m, i)\n",
    "            else:\n",
    "                update(2 * o + 1, m + 1, r, i)\n",
    "            maintain(o, l, r)\n",
    "\n",
    "        build(1, 1, n)\n",
    "        res = []\n",
    "        for i, c in zip(queryIndices, queryCharacters):\n",
    "            s[i] = c\n",
    "            update(1, 1, n, i + 1)\n",
    "            res.append(mx[1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeating(self, s: str, queryCharacters: str, queryIndices: List[int]) -> List[int]:\n",
    "        s = list(s)\n",
    "        n = len(s)\n",
    "        pre = [0] * (4 * n)\n",
    "        suf = [0] * (4 * n)\n",
    "        mx = [0] * (4 * n)\n",
    "\n",
    "        def maintain(o: int, l: int, r: int) -> None:\n",
    "            pre[o] = pre[o * 2]\n",
    "            suf[o] = suf[o * 2 + 1]\n",
    "            mx[o] = max(mx[o * 2], mx[o * 2 + 1])\n",
    "            m = (l + r) // 2\n",
    "            if s[m - 1] == s[m]:\n",
    "                if suf[o * 2] == m - l + 1:\n",
    "                    pre[o] += pre[o * 2 + 1]\n",
    "                if pre[o * 2 + 1] == r - m:\n",
    "                    suf[o] += suf[o * 2]\n",
    "                mx[o] = max(mx[o], suf[o * 2] + pre[o * 2 + 1])\n",
    "\n",
    "        def build(o: int, l: int, r: int) -> None:\n",
    "            if l == r:\n",
    "                pre[o] = suf[o] = mx[o] = 1\n",
    "                return\n",
    "            m = (l + r) // 2\n",
    "            build(o * 2, l, m)\n",
    "            build(o * 2 + 1, m + 1, r)\n",
    "            maintain(o, l, r)\n",
    "\n",
    "        def update(o: int, l: int, r: int, i: int) -> None:\n",
    "            if l == r: return\n",
    "            m = (l + r) // 2\n",
    "            if i <= m:\n",
    "                update(o * 2, l, m, i)\n",
    "            else:\n",
    "                update(o * 2 + 1, m + 1, r, i)\n",
    "            maintain(o, l, r)\n",
    "\n",
    "        build(1, 1, n)\n",
    "        ans = []\n",
    "        for c, i in zip(queryCharacters, queryIndices):\n",
    "            s[i] = c\n",
    "            update(1, 1, n, i + 1)\n",
    "            ans.append(mx[1])\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeating(self, s: str, queryCharacters: str, queryIndices: List[int]) -> List[int]:\n",
    "        s = list(s)\n",
    "        n = len(s)\n",
    "        pre = [0] * (4 * n)\n",
    "        suf = [0] * (4 * n)\n",
    "        mx = [0] * (4 * n)\n",
    "\n",
    "        def maintain(o: int, l: int, r: int) -> None:\n",
    "            pre[o] = pre[o * 2]\n",
    "            suf[o] = suf[o * 2 + 1]\n",
    "            mx[o] = max(mx[o * 2], mx[o * 2 + 1])\n",
    "            m = (l + r) // 2\n",
    "            if s[m - 1] == s[m]:  # 中间字符相同，可以合并\n",
    "                if suf[o * 2] == m - l + 1:\n",
    "                    pre[o] += pre[o * 2 + 1]\n",
    "                if pre[o * 2 + 1] == r - m:\n",
    "                    suf[o] += suf[o * 2]\n",
    "                mx[o] = max(mx[o], suf[o * 2] + pre[o * 2 + 1])\n",
    "\n",
    "        def build(o: int, l: int, r: int) -> None:\n",
    "            if l == r:\n",
    "                pre[o] = suf[o] = mx[o] = 1\n",
    "                return\n",
    "            m = (l + r) // 2\n",
    "            build(o * 2, l, m)\n",
    "            build(o * 2 + 1, m + 1, r)\n",
    "            maintain(o, l, r)\n",
    "\n",
    "        def update(o: int, l: int, r: int, i: int) -> None:\n",
    "            if l == r: return\n",
    "            m = (l + r) // 2\n",
    "            if i <= m:\n",
    "                update(o * 2, l, m, i)\n",
    "            else:\n",
    "                update(o * 2 + 1, m + 1, r, i)\n",
    "            maintain(o, l, r)\n",
    "\n",
    "        build(1, 1, n)\n",
    "        ans = []\n",
    "        for c, i in zip(queryCharacters, queryIndices):\n",
    "            s[i] = c\n",
    "            update(1, 1, n, i + 1)\n",
    "            ans.append(mx[1])\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeating(self, s: str, queryCharacters: str, queryIndices: List[int]) -> List[int]:\n",
    "        s = list(s)\n",
    "        n = len(s)\n",
    "        pre = [0] * (4 * n)\n",
    "        suf = [0] * (4 * n)\n",
    "        mx = [0] * (4 * n)\n",
    "\n",
    "        def maintain(o: int, l: int, r: int) -> None:\n",
    "            pre[o] = pre[o * 2]\n",
    "            suf[o] = suf[o * 2 + 1]\n",
    "            mx[o] = max(mx[o * 2], mx[o * 2 + 1])\n",
    "            m = (l + r) // 2\n",
    "            if s[m - 1] == s[m]:  # 中间字符相同，可以合并\n",
    "                if suf[o * 2] == m - l + 1:\n",
    "                    pre[o] += pre[o * 2 + 1]\n",
    "                if pre[o * 2 + 1] == r - m:\n",
    "                    suf[o] += suf[o * 2]\n",
    "                mx[o] = max(mx[o], suf[o * 2] + pre[o * 2 + 1])\n",
    "\n",
    "        def build(o: int, l: int, r: int) -> None:\n",
    "            if l == r:\n",
    "                pre[o] = suf[o] = mx[o] = 1\n",
    "                return\n",
    "            m = (l + r) // 2\n",
    "            build(o * 2, l, m)\n",
    "            build(o * 2 + 1, m + 1, r)\n",
    "            maintain(o, l, r)\n",
    "\n",
    "        def update(o: int, l: int, r: int, i: int) -> None:\n",
    "            if l == r: return\n",
    "            m = (l + r) // 2\n",
    "            if i <= m:\n",
    "                update(o * 2, l, m, i)\n",
    "            else:\n",
    "                update(o * 2 + 1, m + 1, r, i)\n",
    "            maintain(o, l, r)\n",
    "\n",
    "        build(1, 1, n)\n",
    "        ans = []\n",
    "        for c, i in zip(queryCharacters, queryIndices):\n",
    "            s[i] = c\n",
    "            update(1, 1, n, i + 1)\n",
    "            ans.append(mx[1])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeating(self, s: str, queryCharacters: str, queryIndices: List[int]) -> List[int]:\n",
    "        s = list(s)\n",
    "        n = len(s)\n",
    "        pre = [0] * (4 * n)\n",
    "        suf = [0] * (4 * n)\n",
    "        mx = [0] * (4 * n)\n",
    "\n",
    "        def maintain(o: int, l: int, r: int) -> None:\n",
    "            pre[o] = pre[o * 2]\n",
    "            suf[o] = suf[o * 2 + 1]\n",
    "            mx[o] = max(mx[o * 2], mx[o * 2 + 1])\n",
    "            m = (l + r) // 2\n",
    "            if s[m - 1] == s[m]:  # 中间字符相同，可以合并\n",
    "                if suf[o * 2] == m - l + 1:\n",
    "                    pre[o] += pre[o * 2 + 1]\n",
    "                if pre[o * 2 + 1] == r - m:\n",
    "                    suf[o] += suf[o * 2]\n",
    "                mx[o] = max(mx[o], suf[o * 2] + pre[o * 2 + 1])\n",
    "\n",
    "        def build(o: int, l: int, r: int) -> None:\n",
    "            if l == r:\n",
    "                pre[o] = suf[o] = mx[o] = 1\n",
    "                return\n",
    "            m = (l + r) // 2\n",
    "            build(o * 2, l, m)\n",
    "            build(o * 2 + 1, m + 1, r)\n",
    "            maintain(o, l, r)\n",
    "\n",
    "        def update(o: int, l: int, r: int, i: int) -> None:\n",
    "            if l == r: return\n",
    "            m = (l + r) // 2\n",
    "            if i <= m:\n",
    "                update(o * 2, l, m, i)\n",
    "            else:\n",
    "                update(o * 2 + 1, m + 1, r, i)\n",
    "            maintain(o, l, r)\n",
    "\n",
    "        build(1, 1, n)\n",
    "        ans = []\n",
    "        for c, i in zip(queryCharacters, queryIndices):\n",
    "            s[i] = c\n",
    "            update(1, 1, n, i + 1)\n",
    "            ans.append(mx[1])\n",
    "        return ans\n",
    "\n",
    "# 作者：灵茶山艾府\n",
    "# 链接：https://leetcode.cn/problems/longest-substring-of-one-repeating-character/solutions/1352584/by-endlesscheng-qpbw/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeating(self, s: str, queryCharacters: str, queryIndices: List[int]) -> List[int]:\n",
    "        s = list(s)\n",
    "        n = len(s)\n",
    "        pre = [0]*(4*n)\n",
    "        suf = [0]*(4*n)\n",
    "        mxc = [0]*(4*n)\n",
    "        def merge(t,l,r):\n",
    "            m = (l+r)>>1\n",
    "            pre[t] = pre[2*t]\n",
    "            suf[t] = suf[2*t+1]\n",
    "            mxc[t] = max(mxc[2*t], mxc[2*t+1])\n",
    "            if(s[m] == s[m+1]):\n",
    "                if(pre[2*t] == m-l+1):\n",
    "                    pre[t] = pre[2*t] + pre[2*t+1]\n",
    "                if(suf[2*t+1] == r - m):\n",
    "                    suf[t] = suf[2*t] + suf[2*t+1]\n",
    "                mxc[t] = max(mxc[t], suf[2*t]+pre[2*t+1])\n",
    "            return\n",
    "        \n",
    "        def build(t,l,r):\n",
    "            if(l == r):\n",
    "                pre[t] = 1\n",
    "                suf[t] = 1\n",
    "                mxc[t] = 1\n",
    "                return\n",
    "            m = (l+r)>>1\n",
    "            build(2*t,l,m)\n",
    "            build(2*t+1,m+1,r)\n",
    "            merge(t,l,r)\n",
    "            return\n",
    "        \n",
    "        def update(t,l,r,i):\n",
    "            if(l == r):\n",
    "                return \n",
    "            m = (l+r)>>1\n",
    "            if(i <= m):\n",
    "                update(2*t,l,m,i)\n",
    "            else:\n",
    "                update(2*t+1,m+1,r,i)\n",
    "            merge(t,l,r)\n",
    "            return\n",
    "\n",
    "        result = []\n",
    "        build(1,0,n-1)\n",
    "        for c,i in zip(queryCharacters, queryIndices):\n",
    "            s[i] = c \n",
    "            update(1,0,n-1,i)\n",
    "            result.append(mxc[1])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeating(self, s: str, queryCharacters: str, queryIndices: List[int]) -> List[int]:\n",
    "        #copy 0x3\n",
    "        s = list(s)\n",
    "        n = len(s)\n",
    "        pre = [0] *(4*n)\n",
    "        suf = [0] *(4*n)\n",
    "        mx = [0] *(4*n)\n",
    "        def maintain(o,l,r):\n",
    "            pre[o] = pre[o*2]\n",
    "            suf[o] = suf[o*2+1]\n",
    "            mx[o] = max(mx[o*2],mx[o*2+1])\n",
    "            m = (l+r)//2\n",
    "            if s[m-1] == s[m]:\n",
    "                if suf[o*2] == m-l+1:\n",
    "                    pre[o] += pre[o*2+1]\n",
    "                if pre[o*2+1] == r-m:\n",
    "                    suf[o] += suf[o*2]\n",
    "                mx[o] = max(mx[o],suf[o*2]+pre[o*2+1])\n",
    "        def build(o,l,r):\n",
    "            if l == r:\n",
    "                pre[o] = suf[o] = mx[o] = 1\n",
    "                return \n",
    "            m = (l+r)//2\n",
    "            build(o*2,l,m)\n",
    "            build(o*2+1,m+1,r)\n",
    "            maintain(o,l,r)\n",
    "        def update(o,l,r,i):\n",
    "            if l==r:\n",
    "                return\n",
    "            m = (l+r)//2\n",
    "            if i <= m:\n",
    "                update(o*2,l,m,i)\n",
    "            else:\n",
    "                update(o*2+1,m+1,r,i)\n",
    "            maintain(o,l,r)\n",
    "\n",
    "        build(1,1,n)\n",
    "        ans = []\n",
    "        for c, i in zip(queryCharacters,queryIndices):\n",
    "            s[i] = c\n",
    "            update(1,1,n,i+1)\n",
    "            ans.append(mx[1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeating(self, s: str, queryCharacters: str, queryIndices: List[int]) -> List[int]:\n",
    "        s = list(s)\n",
    "        n = len(s)\n",
    "        \n",
    "        pre = [0] * (4 * n)\n",
    "        suf = [0] * (4 * n)\n",
    "        mx = [0] * (4 * n)\n",
    "\n",
    "        def build(start, end, idx):\n",
    "            if start == end:\n",
    "                pre[idx] = suf[idx] = mx[idx] = 1\n",
    "                return \n",
    "\n",
    "            m = (start + end) // 2\n",
    "            build(start, m, idx * 2)\n",
    "            build(m + 1, end, idx * 2 + 1)\n",
    "\n",
    "            pre[idx] = pre[idx * 2]\n",
    "            suf[idx] = suf[idx * 2 + 1]\n",
    "            mx[idx] = max(mx[idx * 2], mx[idx * 2 + 1])\n",
    "\n",
    "            if s[m] == s[m + 1]:\n",
    "                if suf[idx * 2] == m - start + 1:\n",
    "                    pre[idx] += pre[idx * 2 + 1]\n",
    "\n",
    "                if pre[idx * 2 + 1] == end - m:\n",
    "                    suf[idx] += suf[idx * 2]\n",
    "\n",
    "                mx[idx] = max(mx[idx], suf[idx * 2] + pre[idx * 2 + 1])\n",
    "\n",
    "        def update(i, start, end, idx):\n",
    "            if start == end:\n",
    "                return\n",
    "\n",
    "            m = (start + end) // 2\n",
    "\n",
    "            if i <= m:\n",
    "                update(i, start, m, idx * 2)\n",
    "            else:\n",
    "                update(i, m + 1, end, idx * 2 + 1)\n",
    "\n",
    "            pre[idx] = pre[idx * 2]\n",
    "            suf[idx] = suf[idx * 2 + 1]\n",
    "            mx[idx] = max(mx[idx * 2], mx[idx * 2 + 1])\n",
    "\n",
    "            if s[m] == s[m + 1]:\n",
    "                if suf[idx * 2] == m - start + 1:\n",
    "                    pre[idx] += pre[idx * 2 + 1]\n",
    "\n",
    "                if pre[idx * 2 + 1] == end - m:\n",
    "                    suf[idx] += suf[idx * 2]\n",
    "\n",
    "                mx[idx] = max(mx[idx], suf[idx * 2] + pre[idx * 2 + 1])\n",
    "\n",
    "        build(0, n - 1, 1)\n",
    "        \n",
    "        k = len(queryCharacters)\n",
    "        ret = [0] * k\n",
    "\n",
    "        for i in range(k):\n",
    "            s[queryIndices[i]] = queryCharacters[i]\n",
    "\n",
    "            update(queryIndices[i], 0, n - 1, 1)\n",
    "            ret[i] = mx[1]\n",
    "\n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestRepeating(self, s: str, queryCharacters: str, queryIndices: List[int]) -> List[int]:\n",
    "        s = list(s)\n",
    "        n = len(s)\n",
    "        pre = [0] * (4 * n)\n",
    "        suf = [0] * (4 * n)\n",
    "        mx = [0] * (4 * n)\n",
    "\n",
    "        def maintain(o: int, l: int, r: int) -> None:\n",
    "            pre[o] = pre[o * 2]\n",
    "            suf[o] = suf[o * 2 + 1]\n",
    "            mx[o] = max(mx[o * 2], mx[o * 2 + 1])\n",
    "            m = (l + r) // 2\n",
    "            if s[m - 1] == s[m]:  # 中间字符相同，可以合并\n",
    "                if suf[o * 2] == m - l + 1:\n",
    "                    pre[o] += pre[o * 2 + 1]\n",
    "                if pre[o * 2 + 1] == r - m:\n",
    "                    suf[o] += suf[o * 2]\n",
    "                mx[o] = max(mx[o], suf[o * 2] + pre[o * 2 + 1])\n",
    "\n",
    "        def build(o: int, l: int, r: int) -> None:\n",
    "            if l == r:\n",
    "                pre[o] = suf[o] = mx[o] = 1\n",
    "                return\n",
    "            m = (l + r) // 2\n",
    "            build(o * 2, l, m)\n",
    "            build(o * 2 + 1, m + 1, r)\n",
    "            maintain(o, l, r)\n",
    "\n",
    "        def update(o: int, l: int, r: int, i: int) -> None:\n",
    "            if l == r: return\n",
    "            m = (l + r) // 2\n",
    "            if i <= m:\n",
    "                update(o * 2, l, m, i)\n",
    "            else:\n",
    "                update(o * 2 + 1, m + 1, r, i)\n",
    "            maintain(o, l, r)\n",
    "\n",
    "        build(1, 1, n)\n",
    "        ans = []\n",
    "        for c, i in zip(queryCharacters, queryIndices):\n",
    "            s[i] = c\n",
    "            update(1, 1, n, i + 1)\n",
    "            ans.append(mx[1])\n",
    "        return ans\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
